LightOJ - 1112 - Curious Robin Hood

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

IDEA: This problem can be solved using BIT. There are three type of query in this problem. First one is point update, second one is also point update, third one is range query. BIT has two functions. One is point update and another is range query.
Before using these functions we need to initialize the tree with zero value.Then update with the array value.As,BIT tree works when its initial values are zero.

CODE: 

#include <bits/stdc++.h>

using namespace std;

#define pii              pair <int,int>
#define pll              pair <long long,long long>
#define sc               scanf
#define pf               printf
#define Pi               2*acos(0.0)
#define ms(a,b)          memset(a, b, sizeof(a))
#define pb(a)            push_back(a)
#define MP               make_pair
#define db               double
#define ll               long long
#define EPS              10E-10
#define ff               first
#define ss               second
#define sqr(x)           (x)*(x)
#define D(x)             cerr<<#x " = "<<(x)<<endl
#define VI               vector <int>
#define DBG              pf("Hi\n")
#define MOD              1000000007
#define CIN              ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0)
#define SZ(a)            (int)a.size()
#define sf(a)            scanf("%d",&a)
#define sfl(a)           scanf("%lld",&a)
#define sff(a,b)         scanf("%d %d",&a,&b)
#define sffl(a,b)        scanf("%lld %lld",&a,&b)
#define sfff(a,b,c)      scanf("%d %d %d",&a,&b,&c)
#define sfffl(a,b,c)     scanf("%lld %lld %lld",&a,&b,&c)
#define stlloop(v)       for(__typeof(v.begin()) it=v.begin();it!=v.end();it++)
#define loop(i,n)        for(int i=0;i<n;i++)
#define loop1(i,n)       for(int i=1;i<=n;i++)
#define REP(i,a,b)       for(int i=a;i<b;i++)
#define RREP(i,a,b)      for(int i=a;i>=b;i--)
#define TEST_CASE(t)     for(int z=1;z<=t;z++)
#define PRINT_CASE       printf("Case %d: ",z)
#define LINE_PRINT_CASE  printf("Case %d:\n",z)
#define CASE_PRINT       cout<<"Case "<<z<<": "
#define all(a)           a.begin(),a.end()
#define intlim           2147483648
#define infinity         (1<<28)
#define ull              unsigned long long
#define gcd(a, b)        __gcd(a, b)
#define lcm(a, b)        ((a)*((b)/gcd(a,b)))

int tree[100008];
int a[100008];



void update(int n,int idx,int val)
{
    idx++;
    while(idx<=n)
    {
        tree[idx]+=val;
        idx+=idx & (-idx);
    }
}

int query(int idx)
{
    int sum=0;
    idx++;
    while(idx>0)
    {
        sum+=tree[idx];
        idx-=idx & (-idx);
    }
    return sum;
}

void BIT(int n)
{
    for(int i=0;i<n;i++)
    {
        update(n,i,a[i]);
    }
}

int main()
{
    int t,z=0;
    sf(t);
    while(t--)
    {
        z++;
        int n,q;
        //cin>>n>>q;
        sf(n);
        sf(q);
        ms(tree,0);
        for(int i=0;i<n;i++)
            sf(a[i]);
        BIT(n);
        LINE_PRINT_CASE;
        loop(i,q)
          {
              /*for(int i=1;i<=n;i++)
              cout<<tree[i]<<" ";
              cout<<endl;
              */
              int x,y,z;
              sf(x);
              if(x==1)
              {
                 sf(y);
                 int ans=query(y);
                 int f= query(y-1);
                 ans=ans-f;
                 int l=((-1)*ans);
                 update(n,y,l);
                 printf("%d\n",ans);
              }
              else if(x==2)
              {
                  sf(y);
                  sf(z);
                  update(n,y,z);
              }
              else
                {
                   sf(y);
                   sf(z);
                   int ans=query(z);
                   ans-=query(y-1);
                   printf("%d\n",ans);
                }
          }
    }
    return 0;
}