线段树

#include<iostream>
#include<cstdio>
using namespace std;
int a[100001],tot;
struct node
{
    int l,r;
    int ll,rr;
    int sum;
}tree[200001];
void build(int l,int r)
{
    int k=++tot;
    tree[k].l=l;
    tree[k].r=r;
    if(l==r-1)
    tree[k].sum=a[l];
    else
    {
        tree[k].ll=tot+1;
        build(l,(l+r)/2);
        tree[k].rr=tot+1;
        build((l+r)/2,r);
        tree[k].sum=tree[tree[k].ll].sum+tree[tree[k].rr].sum;
    }
}
int find(int k,int x,int y)
{
    if(x<=tree[k].l&&y>=tree[k].r)
    return tree[k].sum;
    int ans=0;
    if(x<(tree[k].l+tree[k].r)/2)ans+=find(tree[k].ll,x,y);
    if(y>(tree[k].l+tree[k].r)/2)ans+=find(tree[k].rr,x,y);
    return ans;
}
void change(int k,int x,int y)
{
    if(tree[k].l==tree[k].r-1)
    tree[k].sum+=y;
    else
    {
        if(x<(tree[k].l+tree[k].r)/2)
        change(tree[k].ll,x,y);
        else
        change(tree[k].rr,x,y);
        tree[k].sum=tree[tree[k].ll].sum+tree[tree[k].rr].sum;
    }
}
int main()
{
    int n,i,j,k;
    scanf("%d",&n);
    for(i=1;i<=n;i++)
    scanf("%d",&a[i]);
    build(1,n+1);
    int p;
    scanf("%d",&p);
    for(i=1;i<=p;i++)
    {
        int x,y,z,w;
        scanf("%d",&z);
        if(z==1)
        {
            scanf("%d%d",&x,&y);
            change(1,x,y);
        }
        else
        {
            scanf("%d%d",&x,&y);
            printf("%d
",find(1,x,y+1));
        }
    }
    return 0;
}