Light OJ 1112 Curious Robin Hood

#include<bits/stdc++.h>
#define M 1000009
using namespace std;
int arr[M];
int tree[4*M];
void init(int node,int b,int e)
{
    if(b==e)
    {
        tree[node]=arr[b];
        return;
    }
    int left=2*node;
    int right=left+1;
    int mid=(b+e)/2;
    init(left,b,mid);
    init(right,mid+1,e);
    tree[node]=tree[left]+tree[right];
}
int query(int node,int b,int e,int i,int j)
{
    if(i>e||j<b)
        return 0;
    if(b>=i&&e<=j)
    {
        return tree[node];
    }
    int left=2*node;
    int right=left+1;
    int mid=(b+e)/2;
    int p1=query(left,b,mid,i,j);
    int p2=query(right,mid+1,e,i,j);
    return (p1+p2);
}
void update(int node,int b,int e,int i,int newvalue)
{
    if(i>e||i<b)
        return;
    if(b>=i&&e<=i)
    {
        tree[node]=newvalue;
        return;
    }
    int left=2*node;
    int right=left+1;
    int mid=(b+e)/2;
    update(left,b,mid,i,newvalue);
    update(right,mid+1,e,i,newvalue);
    tree[node]=tree[left]+tree[right];
}
int main()
{
    int test;
    scanf("%d",&test);
    for(int k=1;k<=test;k++)
    {
        int m,n;
        scanf("%d %d",&n,&m);
        for(int i=0;i<n;i++)
        {
            scanf("%d",&arr[i]);
        }
        printf("Case %d:\n",k);
        init(1,0,n-1);
        for(int j=1;j<=m;j++)
        {
            int option;
            scanf("%d",&option);
            if(option==1)
            {
                int index;
                scanf("%d",&index);
                printf("%d\n",arr[index]);
                arr[index]=0;
                update(1,0,n-1,index,arr[index]);
            }
            else if(option==2)
            {
                int index,amount;
                scanf("%d %d",&index,&amount);
                arr[index]=arr[index]+amount;
                update(1,0,n-1,index,arr[index]);
            }
            else
            {
                int a,b;
                scanf("%d %d",&a,&b);
                printf("%d\n",query(1,0,n-1,a,b));
            }
        }
    }
    return 0;
}