已经 debug 过了，建树没有问题，应该是 sum 函数的问题

#include<bits/stdc++.h>
#define ll long long
using namespace std;
mt19937 myrand(time(0));
inline ll read(){
	ll x=0,w=1;
	char ch=0;
	while(ch<'0'||ch>'9'){
		if(ch=='-')w=-1;
		ch=getchar();
	}
	while(ch>='0'&&ch<='9'){
		x=x*10+(ch-'0');
		ch=getchar();
	}
	return x*w;
}
void write(ll x){
	if(x<0){
		putchar('-');
		x=-x;
	}
	static int sta[35];
	int top=0;
	do{
		sta[top++]=x%10,x/=10;
	}while(x);
	while(top)putchar(sta[--top]+'0');
}
ll t[4000005],n,m,a[1000005],lazy[400005];
void build(ll l,ll r,ll p){
	if(l==r){
		t[p]=a[l];
		return;
	}
	ll tmp=l+((r-l)>>1);
	build(l,tmp,p<<1);build(tmp+1,r,(p<<1)|1);
	t[p]=t[p<<1]+t[(p<<1)|1];
}
void update(ll l,ll r,ll c,ll s,ll t1,ll p){
	if(l<=s&&r>=t1){
		t[p]+=(t1-s+1)*c;
		lazy[p]+=c;
		return;
	}
	ll tmp=s+((t1-s)>>1);
	if(lazy[p]){
		t[p<<1]+=lazy[p]*(tmp-s+1);
		t[(p<<1)|1]+=lazy[p]*(t1-tmp);
		lazy[p<<1]+=lazy[p];
		lazy[(p<<1)|1]+=lazy[p];
	}
	lazy[p]=0;
	if(l<=tmp){
		update(l,r,c,s,tmp,p<<1);
	}
	if(r>tmp){
		update(l,r,c,tmp+1,t1,(p<<1)|1);
	}
	t[p]=t[p<<1]+t[(p<<1)|1];
}
ll sum(ll l,ll r,ll s,ll t1,ll p){
	ll ret=0;
	if(l<=s&&r>=t1)return t[p];
	ll tmp=s+((t1-s)>>1);
	if(lazy[p]){
		t[p<<1]+=lazy[p]*(tmp-s+1);
		t[(p<<1)|1]+=lazy[p]*(t1-tmp);
		lazy[p<<1]+=lazy[p];
		lazy[(p<<1)|1]+=lazy[p];
	}
	lazy[p]=0;
	if(l<=tmp){
		ret=sum(l,r,s,tmp,p<<1);
	}
	if(r>tmp){
		ret+=sum(l,r,tmp+1,t1,(p<<1)|1);
	}
	return ret;
}
int main(){
	n=read();m=read();
	for(int i=1;i<=n;i++)a[i]=read();
	build(1,n,1);
	while(m--){
		if(read()==1){
			update(read(),read(),read(),1,n,1);
		}else{
			write(sum(read(),read(),1,n,1));
			puts("");
		}
	}
	return 0;
}