尝试用标记永久化，样例过了，测试点3TLE,其他都是WA

#include<iostream>
using namespace std;
const int N=1e6+1;
struct seg {
	int l,r;
	int add;
	long long sum;
} t[N<<2];
int n,m;
void build(int idx,int L,int R) {
	int mid=(L+R)/2;
	t[idx].l=L;
	t[idx].r=R;
	if(L!=R) {
		build(idx*2,L,mid);
		build(idx*2+1,mid+1,R);
	}
}
void update(int idx,int L,int R,int p) {
	if(t[idx].l==t[idx].r) {
		t[idx].sum+=p;
		return ;
	}
	if(t[idx].l>=L&&t[idx].r<=R) {
		t[idx].add=p;
		return ;
	}
	if((t[idx].l+t[idx].r)/2>=L) {
		update(idx*2,L,R,p);
	}
	if((t[idx].l+t[idx].r)/2+1<=R) {
		update(idx*2+1,L,R,p);
	}
	t[idx].sum=t[idx*2+1].sum+t[idx*2].sum;
}
long long query(int idx,int L,int R,int v) {
	long long res=v;
	int mid=(t[idx].l+t[idx].r)/2;
	if(t[idx].l==t[idx].r) {
		return res+t[idx].sum;
	}
	if(mid>=L) {
		res=query(idx*2,L,R,res+t[idx].add*(mid-L+1));
	}
	if(mid+1<=R) {
		res=query(idx*2+1,L,R,res+t[idx].add*(R-mid));
	}
	return res;
}
int main() {
	cin>>n;
	cin>>m;
	build(1,1,n);
	for(int i=1; i<=n; i++) {
		int leef;
		cin>>leef;
		update(1,i,i,leef);
	}

	for(int i=1; i<=m; i++) {
		int opt;
		cin>>opt;
		if(opt==2) {
			int l,r;
			cin>>l>>r;
			long long res=query(1,l,r,0);
			cout<<res<<endl;
		}
		if(opt==1) {
			int l,r,p;
			cin>>l>>r>>p;
			update(1,l,r,p);
		}
	}
	return 0;
}