Fenwick Tree (Binary Index Tree) - Quick Tutorial and Source Code Explanation
In this tutorial we’ll discuss a computer science data structure called "Fenwick Tree", also known as "Binary Index Tree". This data structure is used to efficiently perform range queries, such as addition, multiplication and XOR. We’ll develop a simple visual explanation of how it works. Then, we’ll dive into the details of how to actually implement it by walking over source code of sum() and update() functions, which run in O(log n) time complexity. Finally, we'll discuss the source code of an algorithm that efficiently populates Binary Index Trees with data in O(n) running time.
Full source code implementation of Fenwick Tree in Java:
https://bitbucket.org/StableSort/play...
The paper by Peter Fenwick: http://citeseerx.ist.psu.edu/viewdoc/...
Wikipedia: https://en.wikipedia.org/wiki/Fenwick...
Written and narrated by Andre Violentyev