Saturday, April 30, 2011

Binary Indexed Tree

Tutorial for Binary indexed tree

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/

7 comments:

  1. really useful in lots of spoj problems...thanks!!

    ReplyDelete
  2. Let's see if I got this:
    For the problem given, a.k.a summing over a given range, this is not a good solution, since we can do O(1) if we simply use partial sums in a temp array (sum(i,j) = partialSum(j) - partialSum(i)).
    Nevertheless, this structure is good when asking different questions about a range (e.g. maximum value in a given range / RMQ ).
    My point is - the given example (taken from topCoder) should have been chosen differently.

    ReplyDelete
    Replies
    1. Well we could of-course do the partial sums for getting sums in a range. However if one were to update the elements of the array then I think the update process would have higher complexity. As mentioned in the problem statement, BIT is useful to do both queries and updates at lower complexity and not just queries or updates.

      As for the RMQ on an array of data with updates, I would also like to know how u would do it using a BIT.

      Delete
  3. thank you so much for this tutorials really helpfull :)!!!!!!!!!!

    would you do a tutorial about maxflow, mincost maxflow, mincut, and convex hull? :D!!!!!

    ReplyDelete
  4. I will be very helpfull if u tell us how we should create the tree given we have an array of
    frequencies.

    ReplyDelete
  5. How to implement the function to find the maximum or minimum of a range of numbers in as a query?

    ReplyDelete
    Replies
    1. Lite man! You are a genius.. U can do it urslf :p

      Delete