线段树【区间求和】-526互联

#include<bits/stdc++.h>
#define maxn 500005
using namespace std;
int n,m;
int a[maxn]; 


struct node{
	int l,r,sum;
};

node tr[4*maxn];


void build(int l,int r,int p)
{
	//对[l,r]区间建立线段树，当前根的编号为p 
	int mid = (l+r)>>1;
	//int mid = s+((t-s)>>1);
	//第一种可能会超出int范围 
	tr[p].l = l;tr[p].r = r;
	if(l==r)
	{
		tr[p].sum = a[l];
		return;
	}
	//递归左右区间建树 
	build(l,mid,p<<1);
	//build(l,mid,p*2)
	build(mid+1,r,p<<1|1);
	//build(m+1,t,p*2+1)
	tr[p].sum = tr[p<<1].sum +tr[p<<1|1].sum;
}


void add(int x,int y,int p)
{
	if(tr[p].l == tr[p].r)
	{
		tr[p].sum += y;return;
	}
	int mid = (tr[p].l + tr[p].r)>>1;
	if(x<=mid)add(x,y,p<<1);
	else add(x,y,p<<1|1);
	tr[p].sum = tr[p<<1].sum +tr[p<<1|1].sum;
}


int getsum(int l,int r,int p)
{
	if(l<=tr[p].l&&r>=tr[p].r)
		return tr[p].sum;
	//当前区间为询问区间的子集时直接返回当前区间的和 
	if(l>tr[p].r||r<tr[p].l) 
		return 0;
	int mid = (tr[p].l + tr[p].r)>>1;
	
	return lala(l,r,p<<1)+lala(l,r,p<<1|1);
	//递归查询左右儿子的交集 
}

int main()
{
	cin>>n>>m;
	for(int i = 1;i<= n;i++)cin>>a[i];
	build(1,n,1);
	for(int i = 1;i<=m;i++)
	{
		int b,x,y;
		cin>>b;
		if(b==1)
		{
			cin>>x>>y;
			add(x,y,1);
		}
		int l,r;
		if(b==2)
		{
			cin>>l>>r;
			cout<<getsum(l,r,1)<<endl;
		}
	}
}