模板

记得开 4 倍空间！！！

Code

#include<bits/stdc++.h>
#define ll long long
#define pf printf
#define sf scanf
using namespace std;
const int N=1e5+7;
int tr[N*4];
int f[N*4];
int a[N];
int n,q;
int l,r,val;
void build(int u,int l,int r){
	if(l==r){
		tr[u]=a[l];
		return;
	}
	int mid=(l+r)/2;
	build(u*2,l,mid);
	build(u*2+1,mid+1,r);
	tr[u]=tr[u*2]+tr[u*2+1];
}
void pushdown(int u,int l,int r){
	if(l==r){
		tr[u]+=f[u];
		f[u]=0;
		return;
	}
	tr[u]+=f[u]*(r-l+1);
	f[u*2]+=f[u];
	f[u*2+1]+=f[u];
	f[u]=0;
}
void add(int u,int L,int R,int l,int r,int val){
	if(l>=L&&r<=R){
		f[u]+=val;
		return;
	}
	int mid=(l+r)/2;
	pushdown(u,l,r);
	if(mid>=L) add(u*2,L,R,l,mid,val);
	if(mid+1<=R) add(u*2+1,L,R,mid+1,r,val);
}
int ask(int u,int L,int R,int l,int r){
	if(l>=L&&r<=R){
		pushdown(u,l,r);
		return tr[u];
	}
	int mid=(l+r)/2;
	int sum=0;
	pushdown(u,l,r);
	if(mid>=L) sum+=ask(u*2,L,R,l,mid);
	if(mid+1<=R) sum+=ask(u*2+1,L,R,mid+1,r);
	return sum;
}
int main(){
	sf("%d",&n);
	for(int i=1;i<=n;i++) sf("%d",&a[i]);
	build(1,1,n);
	sf("%d",&q);
	while(q--){
		int op;
		sf("%d%d%d",&op,&l,&r);
		if(op==1){
			sf("%d",&val);
			add(1,l,r,1,n,val);
		}else{
			pf("%d\n",ask(1,l,r,1,n));
		}
	}
	//利用线段树进行一些操作 
}

线段树合并

参考博客

经验

法阵（线段树降 \(\log\)）