Binary Indexed Tree

Tutorial for Binary indexed tree

http://www.topcoder.com/tc?module=Static&d1=tutorials&d2=binaryIndexedTrees

Here i am not giving a tutorial of binary indexed tree. We can use the data structure without knowing how it works. All we need to know is what it does.

Binary Indexed Tree (BIT)

Given a large array. BIT helps us to do the following

1. Update any element a[i] in O(log(n))

2. Query the cumulative value in O(log(n)). query(i) = summation a[k] k=1,2,3,....i

It is faster than segment trees.

#define MAX 100007
int T[MAX+1]; //Define a space for BIT


//function to update
void update(int idx, int val)
{
    while(idx<=MAX)
    {
        T[idx]+=val;
        idx+=(idx&-idx);
    }
}






//function to query
int query(int idx)
{
    int sum=0;
    while(idx>0)
    {
        sum+=T[idx];
        idx-=(idx&-idx);
    }
    return sum;
}

Remember you should never query or update on the 0th element.

that gives an error because your elements are a[1] , a[2] , ....a[n]

so be careful with that.

Some problems you can do with it are:

http://www.topcoder.com/stat?c=problem_statement&pm=6551&rd=9990

http://www.spoj.pl/problems/INVCNT/

https://www.spoj.pl/problems/MCHAOS/

http://www.codechef.com/APRIL11/problems/SPREAD/