P3372求调

#include<bits/stdc++.h>
#define ll long long
using namespace std;
ll n,m,a[10100000],x,y,k,z[10100000],t[10100000];
void down(ll d,ll l,ll r){
	if(z[d]){
		ll q=d*2,w=d*2+1,f=(l+r)/2;
		z[q]+=z[d];
		z[w]+=z[d];
		t[q]+=z[d]*(f-l+1);
		t[w]+=z[d]*(r-f);
		z[d]=0; 
	}
}
void qw(ll d,ll l,ll r){
	if(r==l){
		t[d]=a[l];
		return;
	}
	ll f=(l+r)/2;
	qw(d*2,l,f);
	qw(d*2+1,f+1,r);
	t[d]=t[d*2]+t[d*2+1];
}
void lazy(ll d,ll l,ll r){
	ll f=(l+r)/2;
	if(x<=l&&r<=y){
		z[d]+=k;
		t[d]+=k*(r-l+1);
		return;
	}
	down(d,l,r);
	if(x<=f){
		lazy(d*2,l,f);
	}
	if(f<y){
		lazy(d*2+1,f+1,r);
	}
	t[d]=t[d*2]+t[d*2+1];
}
ll findl(ll d,ll l,ll r){
	ll s=0;
	if(x<=l&&r<=y){
		return t[d];
	}
	ll f=(l+r)/2;
	//cout<<x<<" "<<f;
	if(x<=f){
		s+=findl(d*2,l,f);
		
	}
	if(f<y){
		s+=findl(d*2+1,f+1,r);
	}
	return s;
}
int main(){
	scanf("%lld%lld",&n,&m);
	for(int i=1;i<=n;i++){
		scanf("%lld",&a[i]);
	}
	qw(1,1,n);
	for(int o=1;o<=m;o++){
		ll q;
		scanf("%lld%lld%lld",&q,&x,&y);
		if(q==1){
			scanf("%lld",&k);
			lazy(1,1,n);
		}
		else{
			printf("%lld\n",findl(1,1,n));
		}
	}
	return 0;
}