1112 - Curious Robin Hood

Problem Link : http://www.lightoj.com/volume_showproblem.php?problem=1112

Solution :

#include<bits/stdc++.h>

#define mx 100001

using namespace std;


int arr[mx];
int tree[mx*4];
int global;

void init(int node, int b,int e)
{
    if(b==e)
    {
        tree[node]=arr[b];
        return;
    }

    int left=2*node;
    int right=(2*node )+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(j<b || i>e) return 0;

    if(b>=i && e<=j)
    {
        return tree[node];
    }

    int left=2*node;
    int right=(2*node)+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 val)
{
    if(i<b || i>e) return ;

    if(b==e)
    {
        global=tree[node];

        tree[node]=val;
        return ;
    }

    int left=2*node;
    int right=(2*node)+1;
    int mid=(b+e)/2;

    update(left,b,mid,i,val);
    update(right,mid+1,e,i,val);

    tree[node]=tree[left]+tree[right];
}

void update1(int node,int b,int e,int i,int val)
{
    if(i<b || i>e) return ;

    if(b==e)
    {
        global=tree[node];

        tree[node]=global+val;
        return ;
    }

    int left=2*node;
    int right=(2*node)+1;
    int mid=(b+e)/2;

    update1(left,b,mid,i,val);
    update1(right,mid+1,e,i,val);

    tree[node]=tree[left]+tree[right];
}



int main()
{

    int t,n,q,l,r,ans,v;
    scanf("%d",&t);

   for(int ca=1;ca<=t;ca++)
   {


       scanf("%d%d",&n,&q);

       for(int i=1;i<=n;i++) scanf("%d",&arr[i]);


       init(1,1,n);



       printf("Case %d:\n",ca);

       for(int i=1;i<=q;i++)
       {
           scanf("%d",&l);

           if(l==1)
           {
               scanf("%d",&r);
               update(1,1,n,r+1,0);
                printf("%d\n",global);
           }
           else if(l==2)
           {
               scanf("%d%d",&r,&v);

               update1(1,1,n,r+1,v);

           }
           else if(l==3)
           {
               scanf("%d%d",&r,&v);
               ans=query(1,1,n,r+1,v+1);
           printf("%d\n",ans);

           }


       }


   }

}