(線分樹単点修正区間クエリ)洛谷P 374【テンプレート】ツリー配列1

#include
#define pii pair
#define ll long long
#define cl(x,y) memset(x,y,sizeof(x))
#define ct cerr<
const int N=1e6+10;
const int mod=1e7+9;
const int maxn=0x3f3f3f3f;
const int minn=0xc0c0c0c0;
const int inf=99999999;
using namespace std;
struct seg
{
	int l,r,sum;
} tree[N<<2];
int a[N];
void build(int i,int l,int r)
{
	tree[i]={l,r,0};
	if(l==r)
	{
		tree[i].sum=a[l];
		return;
	}
	int mid=(l+r)>>1;
	build(i<<1,l,mid);
	build(i<<1|1,mid+1,r);
	tree[i].sum=tree[i<<1].sum+tree[i<<1|1].sum;	
}
void add(int i,int dis,int k)
{
	if(tree[i].l==tree[i].r)
	{
		tree[i].sum+=k;
		return;
	}
	int mid=(tree[i].l+tree[i].r)>>1;
	if(dis<=mid)
		add(i<<1,dis,k);
	else
		add(i<<1|1,dis,k);
	tree[i].sum=tree[i<<1].sum+tree[i<<1|1].sum;
	return;
}
int search(int i,int l,int r)
{
	if(tree[i].l>=l && tree[i].r<=r)
		return tree[i].sum;
	if(tree[i].l>r || tree[i].r<l)
		return 0;
	int res=0,mid=(tree[i].l+tree[i].r)>>1;
	if(mid>=l)
		res+=search(i<<1,l,r);
	if(mid<=r)
		res+=search(i<<1|1,l,r);
	return res;
}
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);cout.tie(0);
	int n,m,i;
	cin>>n>>m;
	for(i=1;i<=n;i++)
		cin>>a[i];
	build(1,1,n);
	while(m--)
	{
		int k,x,y;
		cin>>k>>x>>y;
		if(k==1)
			add(1,x,y);
		else if(k==2)
		{
			int ans=search(1,x,y);
			cout<<ans<<endl;
		}
	}
	return 0;
}