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.


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.

Happy Coding!!!

I’ve written an explanation of BIT, different ways in which they may be used and provided implementation here:

If you want to know intuition behind Binary Indexed Tree, follow this link. It is well described.


please provide some link for BIT based problems…

You can also read this paper (written by you!!).