Fenwick Tree (Binary Indexed Tree)

To understand Fenwick trees you will need to first understand binary representation of numbers and basic bit manipulation, a previous post of mine covers these topics.

Resources:

1. Video overview
2. Video explanation
3. Implementation

Takeaways:

• A Fenwick tree is a data structure that can efficiently calculate prefix sums for a range of numbers, whilst also supporting updates efficiently.
  • A prefix sum is essentially a running total of a range of numbers. The prefix sums of sourceArray = [1,2,3,4,5] are prefixSumArray = [1,3,6,10,15].
  • Arrays, like Fenwick trees, can be used for prefix sums.
  • Using the previous example: calculating the prefix sum at prefixSumArray[i] is an O(1) operation.
  • Updating an element at sourceArray[i] means we also need to update our prefix sum array. This is an expensive operation that takes O(n) - because we need to update n prefixes in prefixSumArray.
  • To construct a prefix sum array takes O(n).
  • By contrast, a Fenwick tree also takes O(n) for construction but is O(log n) for both updates & prefix sum operations.
  • Space complexity of a Fenwick tree is O(n)
• A Fenwick tree is an array that stores, at each index, prefix sums of n elements from a source array
  • This is different to a prefix array because each index has a relation to other indices. Because of this, at each index we do not store the prefix sum of all elements that precede it - instead we store the prefix sum of all it's child indices.
  • This relationship between indices means that at each index in a Fenwick tree we store data that is the sum of n indices, but not necessarily the sum of all the indices up to and including i (which is what a prefix array does).
• A Fenwick tree is actually not a tree structure, instead the tree is stored as an array that represents a tree.
  • Index 0 of the array is the virtual root node of the tree and is not used for data (prefixes)
  • Half of the elements have a range of responsibility for 1 element
  • A quarter of elements have responsibility for 2 elements
  • An eighth of elements have a responsibility for 4 elements
  • A sixteenth of the elements have a responsibility for 8 elements
  • And so on...
• Range of responsibility, in this context, means that the elements contain a prefix sum for the range of elements they are responsible for.
  • This means, unlike prefix arrays, we do not need to check every element in a range of indices to calculate a prefix sum.
• A Fenwick tree does this dividing/assigning of range of responsibility based on the binary representation of the indices of the array. This works like so:
  • If the furthest right bit of i is set to 1 (1) then the same data from the source array is stored at the same position in the Fenwick tree array. These are the "half of elements" and have a range of responsibility of 1 - as they contain the exact values from the source array.
  • If the first bit of i is 0 (0) but the second bit is set to 1 (2) then the range of responsibility is 2. These are the "quarter of elements". Again, the data is stored at the same index in the Fenwick tree array as it was in the source array - however this time the data will be the sum of sourceArray[i] + sourceArray[i - 1] (indices of the "quarter of elements" are parents of the "half of elements" indices).
  • If the first two bits of i are 0 but the third bit is set to 1 (4) then the range of responsibility is 4. These are the "eighth of elements". These elements are the parents of the "quarter of elements" and grandparents of the "half of elements". The sum of the previous 3 elements, and the current element (sourceArray[i]), are stored in the Fenwick tree array at the current index.
  • This process continues until all indices are filled with sums of elements from the source array. The Fenwick tree will now contain elements that are all prefixes across a certain range of elements (1,2,4,8 etc.).
• To calculate a prefix sum using a Fenwick tree, if we are given an index i we simply loop while (i > 0) (0 is our root node with no data in it) and inside the loop add the current element at i to a running sum sum += tree[i]. Then we decrement i by flipping it's last set bit to 0. The process is repeated until all of i's bits are flipped to 0.
  • Flipping last set bits like this, means we traverse up the tree to i's parent & any ancestor nodes (indices). As indices can have a range of responsibility larger than one, we do not have to visit all the elements in a range to calculate the prefix sum. Just i and it's ancestors in the tree.
• To increase or decrease the value in a Fenwick tree stored at an index i by an integer x, the logic is very similar to prefix sum:
  • while(i < tree.Length) we add x to the current index tree[i] += x.
  • After updating the current index, we need to update all of i's ancestors.
  • To do this we add the last set bit to of i to itself (so 0010 (2) becomes 0100 (4)).
  • We continue adding x to tree[i] and incrementing i whilst i is smaller than our tree length (to prevent going out of bounds).
• The logic in our add operation (just described), of incrementing i by it's last set bit (which leaves us with an index representing i's parent), is used when constructing a Fenwick tree in O(n). We loop over every element in the source array, find i's parent and populate data in our tree. This helps to effectively partition our Fenwick tree array into indices with ranges of responsibility.

Below you will find a Fenwick tree implementation with test cases. There are other basic operations a Fenwick tree can support by reusing the prefix sum or add operations, some of these have been implemented below:

As always, if you found any errors in this post please let me know!