3372 70分求调

#include<bits/stdc++.h>
#define hl h<<1
#define hr h<<1|1
using namespace std;
const int N=5e5+1; 
int n,m,id,x,y,k,s[N];
struct jntm{
	int l,r,sum,add;
}df[N*4];
void pushup(int h){
	df[h].sum=df[hl].sum+df[hr].sum;
	return;
}
void build(int h,int l,int r){
	df[h]={l,r,s[l]};
	if(l==r) return;		
	int cnt=l+r>>1;
	build(hl,l,cnt);
	build(hr,cnt+1,r);
	pushup(h);
}
void pushdown(int h){
	if(df[h].add){
		df[hl].sum+=(df[hl].r-df[hl].l+1)*df[h].add;
		df[hr].sum+=(df[hr].r-df[hr].l+1)*df[h].add;
		df[hl].add+=df[h].add;
		df[hr].add+=df[h].add;
		df[h].add=0;
	}
}
void updata(int h,int x,int y,int k){
	if(df[h].l>=x&&df[h].r<=y){
		df[h].sum+=(df[h].r-df[h].l+1)*k;
		df[h].add+=k;
		return;
	}
	pushdown(h);
	int cnt=df[h].l+df[h].r>>1;
	if(x<=cnt) updata(hl,x,y,k);
	if(y>cnt) updata(hr,x,y,k);
	pushup(h);
}
int query(int h,int x,int y){
	if(df[h].l>=x&&df[h].r<=y) return df[h].sum;
	pushdown(h);
	int cnt=df[h].l+df[h].r>>1;
	int sum=0;
	if(x<=cnt) sum+=query(hl,x,y);
	if(y>cnt) sum+=query(hr,x,y);
	return sum;
}
int main(){
	cin>>n>>m;
	for(int i=1;i<=n;i++) cin>>s[i];
	build(1,1,n);
	while(m--){
		cin>>id;
		if(id==1){
			cin>>x>>y>>k;
			updata(1,x,y,k);
		} 
		if(id==2){
			cin>>x>>y;
			cout<<query(1,x,y)<<endl;
		} 
	}
	return 0;
}