线段树

#include<iostream>
using namespace std;
int n,m;
const int N=100010;
int a[N];
struct tree{
	int l;
	int r;
	int sum;
}tr[4*N];
void push_up(int u)
{
	tr[u].sum=tr[u<<1].sum+tr[u<<1|1].sum;//更新区间和
}
int build(int u,int l,int r)
{
	if(l==r)tr[u]={l,r,a[r]};
	else {
		int m=l+r>>1;
		tr[u]={l,r};//给节点赋初值
		build(u<<1,l,m);
		build(u<<1|1,m+1,r);
		push_up(u);
	}
}
int query(int u,int l,int r)
{
	if(tr[u].l>=l&&tr[u].r<=r)return tr[u].sum;//如果该区间（l,r）被tr[u]包含就返回tr[u].sum;
    int m=tr[u].l+tr[u].r>>1;
    int sum=0;
    if(l<=m)sum+=query(u<<1,l,r);//判断一下该区间左端点是不是在tr[u]区间的左半边
    if(r>=m+1)sum+=query(u<<1|1,l,r);//
    return sum;
}
void modif(int u,int x,int v)
{
	if(tr[u].r==tr[u].l)tr[u].sum+=v;//如果是叶节点直接加上v
        //否则的话就判断一下，哪些区间需要加上v
	else{
		int m=tr[u].l+tr[u].r>>1;
		if(x<=m)
		{
			modif(u<<1,x,v);
		}
        else
		{
			modif(u<<1|1,x,v);
		}
		push_up(u);
	}

}
int main()
{
	cin>>n>>m;
	for(int i=1;i<=n;i++)
	{
		cin>>a[i];
	}
	build(1,1,n);
	while(m--)
	{
		int k,x,y;
		cin>>k>>x>>y;
		if(k==0){
			cout<<query(1,x,y)<<endl;
		}
		else {
			modif(1,x,y);
		}
	}
	return 0;
}