You are given an array, and you should be able to modify elements and find the sum of a range in the array. Fenwick trees, or Binary Indexed trees (BIT) accomplish this in logarithmic time per operation, and can be modified to support a variety of different operations.
Each index is assigned a range to cover based on its lowest set bit (LSB): the rightmost 1 in its binary representation.
For example, The LSB(10110) (22 in binary) would be 00010 (2 in binary), so index 22 would cover a range of size 2: indicies [21, 22].
The indicies of the nodes that cover any given index must satisfy two conditions. First, it must be greater than or equal to that index. Second, j - LSB(j) must be less than or equal to i. Listing out the nodes that satisfy this condition will give a pattern. For this example, the index 85 (1010101 in binary) is used.
| 1010101 | 1010110 | 1011000 |
|---|---|---|
| 1100000 | 10000000 | 100000000 |
| 1000000000 | 10000000000 | 100000000000 |
All of these numbers are greater or equal than 1010101, and when their last bits are subtracted, they result in a number less than 1010101. There is a simple process to iterate through these numbers:
Start at the index being updated. Update this node, then add the lowest set bit of the index to the current index (for example, the lowest set bit of 9, 1001, would be 1). Repeat until the index is greater than the array size. Click on each step to see the process.
Step 1 Step 2 Step 3 Step 4
In this visualization, each node points to the greatest index less than it that it doesn't cover. For example, node 10 covers [9, 10], so it would point to node 8. Node 24 covers [17, 24], so it points to 16.
To take the sum of some prefix, just iterate until you reach the root: node zero. If the array is of size N, this will take at most lg(N) iterations: to get a better idea of why this is true, look at the structure of the tree.
You are always going to the right, so you iterate through a node of each size (1, 2, 4, 8, etc.) at most once each. The sizes of these nodes must sum to N, so at most lg(N) are iterated through.
In this small example, the path from node 7 to node 0 is highlighted.