The Fenwick Tree is an elegant data structuring technique that helps solve the following problem. Given an array of numbers we would like to be able to:
- Update the element at a given position.
- Answer range sum queries.
The Fenwick tree is very easy to implement but it can be intimidating to get your head around it the first time you encounter it. This post is hopefully going to help you better understand this data structure.
Approach 1
We can use prefix sums to answer range queries in constant time but updating a position may require touching all positions in the worst case. So updates in this way are expensive.
In the usual array representation every position is responsible for itself. That is, every position remembers the value stored in it and that is it. The Fenwick Tree takes this idea of responsibility a bit further
Approach 2
We still use prefix sums but we think of each position as being responsible for a whole range ending at that position. First take a look at the diagram below. The vertical line segments are the ranges for which positions are responsible. If we take a position, write it in binary, remove all 1-bits and keep only the lowest (least significant) 1-bit then the resulting number gives the size of the range for which the position is responsible. For example, if the position is 6 (110 in binary) then the size of the range for which 6 is responsible is 2. In other words, position 6 is responsible for itself and the position before it: the range is [5..6]. Note that the size of a range is always a power of 2.
This idea of responsibility allows us to partition any prefix of the array into a union of disjoint ranges. Let's take the prefix ending at position 10 (in decimal). 10 is written as 1010 in binary. By the argument above we can say that 10 is responsible for the range [9..10]. Now we subtract the size of this range from 10 to get 8. Note that this is equivalent to removing the lowest 1-bit from 1010: 1010 becomes 1000 which is equal to 8. Now we repeat with 8 which is responsible for the range [1..8]. We remove the lowest 1-bit from 8 to get 0 and so we have partitioned the entire prefix.
The sizes of these ranges follow directly from the base-2 representation of the position. The position 10 is written as 1010 in binary, which is equal to $2^3+2^2=8+2$ and these are the ranges that we got. So nothing fancy really.
We need $\log N$ bits to represent an integer $N$ in binary, so this partitioning process takes time $O(\log N)$. This allows us to get a prefix sum in $O(\log N)$ time. Worse than the bound we got by using the first approach but this idea of responsibility is going to allow us to speed up the running time of updates.
To update a position we have to find the ranges that are responsible for it (note that a range can be represented by the position at which it ends) and update them. When a position was responsible for itself only we updated that position but now a position is responsible for itself and other positions as well.
Let us look at responsibility again. Take this bit pattern for example: 1011. If we do a query at position 1100 it gets us to position 1000 (remove lowest 1-bit) afterwards. This means that the range for which position 1100 is responsible starts at 1000 and ends at 1100. Now our bit pattern, 1011, is included in this range and so when we update position 1011 we should update 1100 as well. When we removed the lowest 1-bit from 1100 it got us to 1000 (this turned the 1 bit into a 0 and everything from 1000 to 1100 will be in the range including positions like 1011). So to get the ranges that are responsible for some position we first find the lowest 0 bit, flip it and clear all 1 bits to its right. Do the same for all 0 bits from lowest to highest. This can be simply achieved by adding the lowest 1-bit to the position each time. The ranges responsible for 1011 are: 1011, 1100, 10000, 100000, etc…
Both queries and updates require finding the lowest 1-bit. This can be done by ANDing the position with its two's complement.
- If p = 1010, p's complement is 0101 + 1 = 0110. 1010 & 0110 = 0010.
But you can come up with other methods to isolate the lowest 1-bit.
The Fenwick tree can be used to handle other types of queries. For example, range updates and point queries. With a bit more cleverness it can also be used to perform range updates and range queries. This is all for this post. I hope that it was informative.
