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:
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]
areprefixSumArray = [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 anO(1)
operation. - Updating an element at
sourceArray[i]
means we also need to update our prefix sum array. This is an expensive operation that takesO(n)
- because we need to updaten
prefixes inprefixSumArray
. - To construct a prefix sum array takes
O(n)
. - By contrast, a Fenwick tree also takes
O(n)
for construction but isO(log n)
for both updates & prefix sum operations. - Space complexity of a Fenwick tree is
O(n)
- A prefix sum is essentially a running total of a range of numbers. The prefix sums of
- 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 includingi
(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 to1
(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
is0
(0) but the second bit is set to1
(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 ofsourceArray[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
are0
but the third bit is set to1
(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.).
- If the furthest right bit of
- To calculate a prefix sum using a Fenwick tree, if we are given an index
i
we simply loopwhile (i > 0)
(0 is our root node with no data in it) and inside the loop add the current element ati
to a running sumsum += tree[i]
. Then we decrementi
by flipping it's last set bit to0
. The process is repeated until all ofi
's bits are flipped to0
.- 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. Justi
and it's ancestors in the tree.
- Flipping last set bits like this, means we traverse up the tree to
- To increase or decrease the value in a Fenwick tree stored at an index
i
by an integerx
, the logic is very similar to prefix sum:-
while(i < tree.Length)
we addx
to the current indextree[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 (so0010
(2) becomes0100
(4)). - We continue adding
x
totree[i]
and incrementingi
whilsti
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 representingi
's parent), is used when constructing a Fenwick tree inO(n)
. We loop over every element in the source array, findi
'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!
Top comments (0)