CommonLounge Archive

Binary Indexed Trees (aka Fenwick Tree)

April 26, 2017

The motivation for binary indexed trees is similar to that of segment trees. However, note that segment trees are much more flexible than binary indexed trees, and usually its true that any problem that can be solved with BIT can be solved with segment trees but not the other way around.

Video tutorial: This is a superb tutorial, giving the motivation, walking through example, and going step-by-step through the pseudocode.

Text tutorial:

The best text tutorial for BIT is on TopCoder. Also, here are implementations of BIT in C++ and Python.

As always, feel free to ask questions or add further information on the topic.

© 2016-2022. All rights reserved.