Fenwick Tree (BIT)
A Binary Indexed Tree stores partial sums in a single array, where each index is responsible for a range determined by its lowest set bit. Prefix-sum query and point update both cost O(log n), with far less code and memory than a full segment tree.
A Fenwick tree (Binary Indexed Tree) uses one array, 1-indexed, where index i is responsible for the sum of a range ending at i whose length equals i's lowest set bit (i & -i). This clever indexing means every prefix sum decomposes into at most O(log n) of these ranges.
To compute prefix sum up to i, repeatedly add tree[i] and strip the lowest set bit (i -= i & -i) until i reaches 0 — each step jumps to a range that exactly covers what remains. To update index i by some delta, repeatedly add delta to tree[i] and add the lowest set bit (i += i & -i) until past the array end — each step touches every range that includes i.
The core trick — i & -i isolates the lowest set bit — is exactly what makes both operations symmetric mirror images of each other, walking the same implicit tree in opposite directions. Compared to a segment tree, a BIT is simpler and faster in practice, but only naturally supports sums/prefix-invertible operations (not min/max, which need a full segment tree).
Operations
| Operation | Complexity |
|---|---|
| prefix sum query | O(log n) |
| point update | O(log n) |
| build from array | O(n log n) or O(n) |
| space | O(n) |
Where it's used
Prefix sums with updates, counting inversions, frequency tables in competitive programming, order-statistics trees.