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/

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

ReplyDeleteLet's see if I got this:

ReplyDeleteFor 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.

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.

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

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

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

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

ReplyDeletefrequencies.

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

ReplyDeleteLite man! You are a genius.. U can do it urslf :p

Delete