Fenwick Tree Basics
A Fenwick tree, or binary indexed tree, maintains running prefix sums while allowing single element updates, both in logarithmic time. It is more compact and simpler to code than a segment tree for sum style queries.
The lowest bit trick
The cleverness lives in the binary representation of indices. Each position is responsible for a block of elements whose length equals the value of its lowest set bit:
- To update an index, add the change, then jump to the next index by adding the lowest set bit, repeating until you pass the end.
- To query a prefix sum, accumulate values, then jump to the previous block by subtracting the lowest set bit, repeating until you reach zero.
Each jump clears or moves one bit, so only a logarithmic number of positions are visited.
When to choose it
Fenwick trees shine for cumulative sums and inversion counting. For more general range queries like minimum, a segment tree is the better fit.
Key idea
Indexing by the lowest set bit lets prefix sums and updates each touch only a logarithmic number of slots.