刚学线段树 ，代码 AC 了 ，但复杂度好像不太对 ，有人知道怎么回事吗 ：

#include<bits/stdc++.h>
#define ll long long
using namespace std;
struct tr{
	ll l,r,la,sum;
}x[800100];
ll n,m,p,a,b,c,s[800100]={},ans=0;
void build(ll le,ll ri,ll id){
	x[id].l=le,x[id].r=ri,x[id].sum=s[ri]-s[le-1];
	if(le==ri) return ;
	build(le,(le+ri)/2,2*id);
	build((le+ri)/2+1,ri,2*id+1);
}
void add(ll id){
	ll le=x[id].l,ri=x[id].r,mid=(le+ri)/2;
	if(a<=le&&ri<=b){x[id].la+=c;return ;}
	x[id].sum+=c*(min(b,ri)-max(a,le)+1);
	x[id*2].la+=x[id].la,x[id*2+1].la+=x[id].la,x[id].sum+=x[id].la*(ri-le+1),x[id].la=0;
	if(a<=mid) add(id*2);
	if(b>mid) add(id*2+1);
}
void que(ll id){
	ll le=x[id].l,ri=x[id].r,mid=(le+ri)/2;
	x[id*2].la+=x[id].la,x[id*2+1].la+=x[id].la,x[id].sum+=x[id].la*(ri-le+1),x[id].la=0;
	if(a<=le&&ri<=b){ans+=x[id].sum;return ;}
	if(a<=mid) que(id*2);
	if(b>mid) que(id*2+1);
}
int main(){
	scanf("%lld%lld",&n,&m);
	for(ll i=1;i<=n;i++) scanf("%lld",&s[i]);
	if(n!=1) n=pow(2,log2(n-1)+1);
	for(ll i=1;i<=n;i++) s[i]=s[i]+s[i-1];
	build(1,n,1);
	while(m--){
		cin>>a;
		if(a==1) scanf("%lld%lld%lld",&a,&b,&c),add(1);
		else scanf("%lld%lld",&a,&b),ans=0,que(1),printf("%lld\n",ans);
	}
}