模板——线段树

#include<iostream>
#include<cstdio>
#define int long long
using namespace std;
int n,Q,q,p,tot,l,r,x,a[1000001],tree[5000001],tag[5000001];
void build(int p,int pl,int pr){//建树 
	if(pl==pr){tree[p]=a[pl];return;}//若已经深入树根，那么直接返回 
	int mid=(pl+pr)>>1;
	if(mid>=1)build(p*2,pl,mid);//递归左子树 
	if(mid<n)build(p*2+1,mid+1,pr);//递归右子树 
	tree[p]=tree[p*2]+tree[p*2+1];
}
void addtag(int p,int l,int r,int x){//打上标记 
	tag[p]+=x;
	tree[p]+=(r-l+1)*x;
}
void push_down(int p,int l,int r){//消除标记 
	if(tag[p]){//如果被标记过 
		int mid=(l+r)>>1;
		addtag(p*2,l,mid,tag[p]);//将标记传递给左子树 
		addtag(p*2+1,mid+1,r,tag[p]);//将标记传递给右子树 
		tag[p]=0;
	}
}
void add(int p,int l,int r,int pl,int pr,int x){//将区间[l,r]增加x 
	if(l<=pl&&pr<=r){//如果递归区间[pl,pr]被原区间包含，那么给它打上标记 
		addtag(p,pl,pr,x);
		return;
	}
	push_down(p,pl,pr);//将当前标记消除 
	int mid=(pl+pr)>>1;
	if(l<=mid)add(p*2,l,r,pl,mid,x);//递归左子树 
	if(mid<r)add(p*2+1,l,r,mid+1,pr,x);//递归右子树 
	tree[p]=tree[p*2]+tree[p*2+1];//合成递归得来结果 
}
int query(int p,int l,int r,int pl,int pr){//查询区间[l,r] 
	if(l<=pl&&pr<=r)return tree[p];
	push_down(p,pl,pr);//消除标记 
	int mid=(pl+pr)>>1,ans=0;
	if(l<=mid)ans+=query(p*2,l,r,pl,mid);//递归左子树 
	if(mid<r) ans+=query(p*2+1,l,r,mid+1,pr);//递归右子树 
	return ans;
}
signed main(){
	scanf("%lld%lld",&n,&Q);
	for(int i=1;i<=n;i++)scanf("%lld",&a[i]);
	build(1,1,n);
	while(Q--){
		scanf("%lld%lld%lld",&q,&l,&r);
		if(q==1)scanf("%lld",&x),add(1,l,r,1,n,x);//将区间[l,r]增加x 
		else printf("%lld\n",query(1,l,r,1,n));//查询区间[l,r] 
	}
}