A Fenwick Tree (Binary Indexed Tree) is an array-based data structure that supports prefix sum queries and point updates in O(log n) time using only O(n) space. It exploits the binary representation of indices to determine which elements each position is responsible for, using bitwise operations for efficient traversal.
vector<int> bit;
void update(int i, int delta, int n) {
for (; i <= n; i += i & (-i)) bit[i] += delta;
}
int query(int i) {
int sum = 0;
for (; i > 0; i -= i & (-i)) sum += bit[i];
return sum;
}
int rangeQuery(int l, int r) { return query(r) - query(l-1); }Index i in a Fenwick Tree is responsible for the range of length (i & -i) — the lowest set bit of i. This allows each index to cover a power-of-two range, enabling efficient prefix sum decomposition.
To add delta to index i, update bit[i] then move to the next responsible index by adding the lowest set bit: i += i & (-i). This updates all ancestors in O(log n) steps.
To get prefix sum [1..i], add bit[i] then move to parent by subtracting lowest set bit: i -= i & (-i). This decomposes the prefix sum into O(log n) non-overlapping ranges.
Fenwick Trees are simpler to code and use less memory than Segment Trees. They only support prefix queries and point updates. Segment Trees support range updates and arbitrary aggregates, making them more general.
Quiz coming soon for this algorithm.