Binary Indexed Tree (BIT)


#include <bits/stdc++.h>

using namespace std;

int a[100000],tree[100000];

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

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

int main ()
{
    int tc,n,q,cas=0;
    cin>>tc;
    while(tc--)
    {
        printf("Case %d:\n",++cas);
        cin>>n>>q;
        memset(tree,0,sizeof tree);
        for(int i=1; i<=n; i++)
        {
            cin>>a[i];
            update(i,a[i],n);
        }
        int ic,idx,v,x,y;
        for(int i=0; i<q; i++)
        {
            cin>>ic;
            if(ic==1)
            {
                cin>>idx;
                idx++;
                update(idx,-a[idx],n);
                printf("%d\n",a[idx]);
                a[idx]=0;
            }

            else if(ic==2)
            {
                cin>>idx>>v;
                idx++;
                update(idx,v,n);
                a[idx]+=v;
            }

            else
            {
                cin>>x>>y;
                printf("%d\n",query(y+1)-query(x));
            }
        }

    }
    return 0;
}


Advertisements