线段树模板

沉淀了很久，总算是掌握了线段树的经典模板了。但是还是需要深刻练习才能反复加深印象呢

//线段树模板
#include<bits/stdc++.h>
using namespace std;
#define int long long


const int N=1e5+10;
int ans[N*4];
int t1[N*4],t2[N*4];
int a[N];//存放输入数据
int n,m;
int tag[N*4];



//查找左右儿子
inline int leftson(int x){
	return x<<1;

}
inline int rightson(int x){
	return x<<1|1;

}

//维护区间关系(前缀和，区间最大值，最小值)
void PushSum(int x){
	ans[x]=ans[leftson(x)]+ans[rightson(x)];
}


void PushMax(int x){
	t1[x]=max(t1[leftson(x)],t1[rightson(x)]);
}

void PushMin(int x){
	t2[x]=min(t2[leftson(x)],t2[rightson(x)]);
}

//建树
void build(int x,int l,int r){
	if(l==r){
		ans[x]=a[l];
		return ;
	}
	int mid=(l+r)>>1;
	build(leftson(x),l,mid);
	build(rightson(x),mid+1,r);

	PushSum(x);
	// PushMax(x);
	// PushMin(x);
	

}


//区间修改

inline void f(int x,int l,int r,int k){
	tag[x]=tag[x]+k;
	ans[x]=ans[x]+k*(r-l+1);
	//这里需要区分是整体加k，还是当前区间所有都加k
}

inline void PushDown(int x,int l,int r){
	int mid=(l+r)>>1;
	f(leftson(x),l,mid,tag[x]);
	f(rightson(x),mid+1,r,tag[x]);
	tag[x]=0;

}

inline void  update(int nl,int nr,int l,int r,int x,int k){
	//nl,nr是要修改的区间
	//l,r是当前节点所存储的区间以及节点的编号
	if(nl<=l&&r<=nr){
		ans[x]+=k*(r-l+1);
		tag[x]+=k;
		return ;
	}
	PushDown(x,l,r);
	int mid=(l+r)>>1;
	if(nl<=mid) update(nl,nr,l,mid,leftson(x),k);
	if(nr>mid) update(nl,nr,mid+1,r,rightson(x),k);
	PushSum(x);

}

//区间查询

int query(int _x,int _y,int l,int r,int x){
	int res=0;
	if(_x<=l&&r<=_y){
		return ans[x];
	}
	int mid=(l+r)>>1;
	PushDown(x,l,r);
	if(_x<=mid){
		res+=query(_x,_y,l,mid,leftson(x));

	}
	if(_y>mid){
		res+=query(_x,_y,mid+1,r,rightson(x));

	}
	return res;
	
}

void solve(){
	cin>>n>>m;
	for(int i=1;i<=n;i++){
		cin>>a[i];

	}
	build(1,1,n);
	for(int i=1;i<=m;i++){
		int op;
		cin>>op;
		if(op==1){
			int x,y,k;
			cin>>x>>y>>k;	
			update(x,y,1,n,1,k);
		}
		else{
			int x,y;
			cin>>x>>y;
			cout<<query(x,y,1,n,1)<<endl;
			
		}
	}
}

signed main(){
	int t=1;
	while(t--){
		solve();
	}
	return 0;

}