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

general
,
1

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
2

This may help:

1 Like
3

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!!!

4

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/

5

If you want to know intuition behind Binary Indexed Tree, follow this link. It is well described. algorithms - BIT: What is the intuition behind a binary indexed tree and how was it thought about? - Computer Science Stack Exchange

2 Likes
6

please provide some link for BIT based problems…

7

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

2 Likes