Please explain me what are binary indexed trees and how do they work.

I am not able to understand how to implement binary indexed trees. I cant understand how they work. If someone could please explain me in detail how to use them along with an example.

Thank you.

4 Likes

This may help:

1 Like

Read the top code tutorial linked by @pranabr ,

And you can see a previous discussion on codechef and there you will find good explanation or discussion , I wrote a sort note on BIT in that discussion so follow the below link.

http://discuss.codechef.com/questions/6306/bit-algorithm?page=1#6307

Happy Coding!!!

I’ve written an explanation of BIT, different ways in which they may be used and provided implementation here:
http://kartikkukreja.wordpress.com/2013/05/11/bit-fenwick-tree-data-structure-c-implementation/
http://kartikkukreja.wordpress.com/2013/12/02/range-updates-with-bit-fenwick-tree/

If you want to know intuition behind Binary Indexed Tree, follow this link. It is well described. http://cs.stackexchange.com/questions/10538/bit-what-is-the-intuition-behind-a-binary-indexed-tree-and-how-was-it-thought-a

2 Likes

please provide some link for BIT based problems…

You can also read this paper http://arxiv.org/pdf/1311.6093.pdf (written by you!!).

2 Likes
//