The idea
A Fenwick tree (binary indexed tree) stores partial sums so that both “add v at position i” and “sum of the first i elements” take O(log n).
Cell i covers the last i & −i elements ending at i, where i & −i is the lowest set bit of i. A prefix sum hops downwards with i −= i & −i; an update hops upwards with i += i & −i.
It is shorter and faster than a segment tree when sums are all you need. A typical use is counting inversions: scan the array, and for each element ask how many earlier elements are larger.
Sample problem
315. Count of Smaller Numbers After Self ↗ Hard
For each element of an array, count how many elements to its right are smaller than it.
nums = [5,2,6,1] output = [2,1,1,0]
Why the solution works
Comparing every pair is O(n²). Scan from right to left instead, so that when an element is reached, everything to its right has already been seen.
Keep a count of the values seen so far, indexed by value. “How many seen values are smaller than x” is then a prefix sum of those counts, and seeing a new value is a point update: exactly the two operations a Fenwick tree does in O(log n).
Values can be huge or negative, so they are first replaced by their rank among the distinct values. i & −i isolates the lowest set bit of i: sum strips it to walk down, add adds it to walk up.
Complexity: O(n log n) time, O(n) memory.
Watch out
- Positions start at 1. With index 0,
i += i & -inever moves. - When values are large, compress them to 1..n first.
- Range sums come from two prefix sums, which only works for operations that can be undone, such as addition.