by Kristoffer Æsøy, December 18, 2021
A Binary Indexed Tree, often referred to as a Fenwick Tree, is one of the more advanced data structures we have available. It is a search tree that allows us to efficiently update elements in an array and calculate prefix sums of that same array. In essence, a BI Tree is rather similar to the Segment Tree data structure, in which we will compare the pros and cons of using the two data structures.
We use BI Trees to achieve better worst-case runtime on the two fundamental operations of calculating prefix sums and updating elements than using a simple array. There are two very easy solutions to this problems using an array:
Calculate the prefix sum of the elements by looping through the array, and updating by simply setting the index of the element to the new value.
Store the sum of the first i-th element at each i-th index in a new array, and then update by looping through the 0 to i-th element of the new array.
No matter which approach you decide to choose you end up with one operation taking constant time O(1), and the other taking O(n) time as you possibly have to traverse the entire array for it. Therefore if you end up getting a lot of the worse query you can get a very slow runtime.
BI Trees aims to improve these results by instead making both operations take O(logn) time. This effectively means that we reduce the worst-case drastically, while there are cases with extremely one-sided query requests where the array approach would be faster.
A natural question then is how do we achieve such runtimes for the two operations? The solution lies in the fact that the tree is taking advantage of how numbers are represented in binary notation.
The fundamental idea of binary is the fact that every integer number can be represented as a sum of powers of 2. An example such as 13 can be deconstructed into 8 + 4 + 1 which is equal to 1·23 + 1·22 + 0·21 + 1·20, hence the binary representation of 13 is 1101. A very interesting observation about an arbitrary number n, is that the length of its binary representation is O(log n), which is the driving motivation for creating the BI Trees. We use it as the basis for the runtime of our prefix sum and update operations.
The beauty of the BI Tree is that it is represented as an array, that is the same size as the input array that we construct the tree from, in addition to a single dummy node that is helpful to 1-index the elements of the array. By doing this it is easier to traverse the tree to find the elements we are interested in.
Instead of storing an element at each node in the tree, we store the sum of n elements that is equal to the power of 2. By following the patterns above we can see that we continuously group up larger and larger sums of elements when possible, and revert back to a smaller power of 2 whenever we can’t store more elements. e do it in this fashion so that we can achieve the prefix sum to a number by looping through the binary representation of that number, and grabbing the sum of an amount of elements equaling the least significant bit each time.
Using an example such as 11,we can achieve the sum of the elements by grabbing the last element (11), the last 2 elements (from 9 to 10) and the sum of 8 elements (from 1 to 8). This perfectly matches the binary representation of 11, 1011. By traversing the number this way we always use at most O(logn) nodes of the tree to both calculate the prefix sum as well as update the value.
Below, we have created a simple implementation of a BI Tree with a working example code in Python. The most significant operations, update() and getSum() are included as well as a helpful construction function.
def get_sum(Tree, i):
result = 0
i = i+1
while i > 0:
# add element to sum
result += Tree[i]
# move to parent node, in sum view
i -= i & (-i)
return result
def update(Tree, n, i, value):
i += 1
while i <= n:
# add new value to current node
Tree[i] += value
# move to parent node, in update view
i += i & (-i)
def construct(array, n):
Tree = [0] * (n+1)
# update the values in the tree to be the values in input array
for i in range(n):
update(Tree, n, i, array[i])
return Tree
input_array = [2, 4, 5, 1, 3]
Tree = construct(input_array, len(input_array))
print("Sum of range [0..2] in array is " + str(get_sum(Tree, 2)))
update(Tree, len(input_array), 1, 3)
print("Sum of range [0..2] in array after update is " + str(get_sum(Tree, 2)))
The short answer is that a BI Tree is not able to do everything a segment tree can. A caveat to the BI Tree is that it needs to perform operations that have an inverse operation. If you instead wanted to use a non-invertible operation, such as max or min, then you would use a Segment Tree as every interval in its tree can be found as a union of disjoint intervals.
However, for the task we presented a BI Tree can be preferable as it is both easier to implement, as well as it uses less space. There are few cases where this space constraint will have a massive impact, but if you create a multidimensional BIT/Segment Tree then the constant factor can create a significant difference.
Included are some online programming problems you can try to implement the BI Tree to solve!
https://open.kattis.com/problems/downtime https://open.kattis.com/problems/justforsidekicks
Fenwick Tree. Brilliant.org. Retrieved 16:20, December 18, 2021, from https://brilliant.org/wiki/fenwick-tree/
Binary Indexed Tree or Fenwick Tree. GeeksforGeeks.org. Retrieved 16:20, December 18, 2021, from https://www.geeksforgeeks.org/binary-indexed-tree-or-fenwick-tree-2/
Fenwick Tree. Wikipedia.org. Retrieved 16:20, December 18, 2021, from https://en.wikipedia.org/wiki/Fenwick_tree