LightOJ 1093 Curious Robinhood

#include <bits/stdc++.h>
#define LL  long long
#define SZ(x) ((int)(x).size())
#define ALL(x) (x).begin(),(x).end()
#define REP(i,n) for(int i=0;i<n;i++)
#define FOR(i,a,b) for(int i=a;i<=b;i++)
#define REV(i,n) for(int i=n-1;i>=0;i--)
#define pri(a) cout << a << endl;
#define prii(a,b) cout << a << " " << b << endl;
using namespace std;
#define sz 100007

int ar[sz],tr[3*sz];

void build(int node, int b, int e)
{
    if(b==e)
    {
        tr[node] = ar[b];
        return;
    }
    int mid = (b+e)>>1;
    int lft = node<<1, rgt = lft + 1;
    build(lft,b,mid);
    build(rgt,mid+1,e);
    tr[node] = tr[lft] + tr[rgt];
}

int query(int node, int b, int e, int i, int j)
{
    if(i<=b and j>=e) return tr[node];
    int mid = (b+e)>>1;
    int lft = node<<1, rgt = lft + 1;
    if(j<=mid) return query(lft,b,mid,i,j);
    else if(i>mid) return query(rgt,mid+1,e,i,j);
    else return (query(lft,b,mid,i,j) + query(rgt,mid+1,e,i,j));
}

void update(int node, int b, int e, int idx, int val)
{
    if(b==e)
    {
        ar[b] += val;
        tr[node] = ar[b];
        return;
    }

    int mid = (b+e)>>1;
    int lft = node<<1, rgt = lft + 1;

    if(idx<=mid) update(lft,b,mid,idx,val);
    else if(idx>mid) update(rgt,mid+1,e,idx,val);
    tr[node] = tr[lft] + tr[rgt];
}


int main()
{
    int T,n,q,x,idx,val,lt,rt,cs=0;
    scanf("%d", &T);
    while(T--)
    {
        printf("Case %d:\n", ++cs);
        scanf("%d%d", &n, &q);

        REP(i,n) scanf("%d", &ar[i+1]);

        build(1,1,n);

        REP(i,q)
        {
            scanf("%d", &x);

            if(x==1)
            {
                scanf("%d", &idx);
                printf("%d\n", ar[idx+1]);
                ar[idx+1] = 0;
                update(1,1,n,idx+1,0);
            }
            else if(x==2)
            {
                scanf("%d%d", &idx, &val);
                update(1,1,n,idx+1,val);
            }
            else if(x==3)
            {
                scanf("%d%d", &lt, &rt);
                printf("%d\n",query(1,1,n,lt+1,rt+1));
            }
        }
    }
    return 0;
}