Fenwick tree (BIT) — prefix sums
Scenario
You need to process dynamic range sum queries. You could write a Segment Tree, but it takes 50 lines of recursive code, requires 4N memory, and has a heavy constant factor overhead.
Is there a way to do O(log N) dynamic range sums in just 5 lines of code?
Why it exists
While Segment Trees are incredibly versatile, their constant factor (recursive calls, 4N memory allocations) makes them somewhat slow. Fenwick trees exist to provide a hyper-optimized, iterative, low-memory alternative for specific algebraic operations (like dynamic prefix sums), allowing programmers to squeeze past exceptionally tight time limits. In software engineering, they are used for maintaining cumulative frequency tables in arithmetic coding or dynamically ranking elements in memory-constrained embedded systems.
Mental model
Think of a Fenwick tree like a system of measuring cups. To get 7 liters, you don't use 7 one-liter cups. You use a 4-liter cup, a 2-liter cup, and a 1-liter cup. A Fenwick tree decomposes array ranges into powers of 2 using binary bits, storing exactly enough 'cups' to reconstruct any prefix sum.
A Fenwick Tree (or Binary Indexed Tree / BIT) is a highly specialized data structure that computes Prefix Sums and handles Point Updates in `O(log N)` time. It uses bitwise operations to traverse a flat array, using exactly `O(N)` memory and running much faster in practice than a Segment Tree.
Explanation
**1. The Core Idea (Binary Decomposition):**
Any number can be represented as a sum of powers of 2. For example, index `13` is `8 + 4 + 1`.
In a Fenwick tree, the array `BIT` doesn't store single elements. Instead, `BIT[i]` stores the sum of a specific range of elements ending at `i`. The length of this range is exactly equal to the *lowest set bit* of `i`.
**2. Isolating the Lowest Set Bit (LSB):**
Through two's complement binary math, you can isolate the lowest 1-bit of an integer `x` using the expression `x & (-x)`.
If `x = 10` (binary `1010`), `x & (-x)` yields `2` (binary `0010`).
**3. Point Update (Adding `val` at index `i`):**
When you update index `i`, you must update `BIT[i]` and every subsequent 'measuring cup' that includes `i`. You do this by continuously adding the LSB to `i` until you reach the end of the array. Adding the LSB mathematically jumps to the index of the next larger power-of-2 interval (the next 'cup') that completely encompasses the current index.
`for (; i <= N; i += (i & -i)) BIT[i] += val;`
**4. Prefix Sum (Sum from `1` to `i`):**
To get the sum up to `i`, you simply add `BIT[i]` to your total, and then strip away the LSB from `i` to jump to the next 'measuring cup', until `i` reaches 0.
`for (; i > 0; i -= (i & -i)) sum += BIT[i];`
**Range Query & Invertible Operations:**
To get the sum of range `[L, R]`, you 'subtract' the prefix: `query(R) - query(L - 1)`. Because Range Queries mathematically require inverting/subtracting a prefix, Fenwick Trees ONLY work for **invertible operations** like Sum or XOR. They cannot be used for Min/Max operations, since you cannot 'subtract' a minimum.
Code examples
Fenwick Tree Implementation
vector<int> BIT;
int N;
// Add 'val' to index 'i' (1-based indexing)
void update(int i, int val) {
for (; i <= N; i += (i & -i)) {
BIT[i] += val;
}
}
// Get sum of array[1...i]
int query(int i) {
int sum = 0;
for (; i > 0; i -= (i & -i)) {
sum += BIT[i];
}
return sum;
}
// Get sum of array[l...r]
int query(int l, int r) {
return query(r) - query(l - 1);
}This is the entire data structure. Notice that Fenwick Trees absolutely MUST use 1-based indexing, because the lowest set bit of 0 is 0, which would cause an infinite loop in the update function.
Key points
- Invertible operations only: Fenwick Trees excel at Sum and XOR, but generally cannot be used for Min/Max.
- 1-based indexing: Never pass 0 into a Fenwick update or query function.
Common mistakes
- Using 0-based indexing: The Fenwick tree bitwise traversal breaks entirely if you pass `i = 0`. `0 & -0` is 0. The loop `i += (i & -i)` will stall at 0 forever. You must either 1-index your arrays or internally offset all indices by `+1`.
Recall questions
- What is the time and space complexity of a Fenwick Tree compared to a Segment Tree?
- What bitwise expression is used to extract the lowest set bit of an integer `i`?
- Why must a Fenwick Tree use 1-based indexing?
Questions & answers
A developer needs to answer Range Minimum Queries (RMQ). They implement a Fenwick Tree instead of a Segment Tree to save memory. Their code fails logic checks. Why?
A standard Fenwick Tree can only handle invertible operations (like addition/subtraction or XOR). To get the sum of `[L, R]`, it calculates `PrefixSum(R) - PrefixSum(L-1)`. You cannot 'subtract' a minimum. Therefore, Fenwick Trees cannot do general RMQ. You must use a Segment Tree or Sparse Table.
Approach: Understand the algebraic requirements (invertibility) of prefix-based data structures.
You are given an array of 100,000 numbers and need to process both Point Updates and Range Sum Queries. However, memory is extremely constrained on the embedded device. Should you use a Segment Tree or a Fenwick Tree?
You should strictly use a Fenwick Tree. A Segment Tree requires an array of size `4 * N` (400,000 integers), while a Fenwick Tree operates completely in-place or requires an array of size exactly `N` (100,000 integers). Both provide O(log N) operations.
Approach: Evaluate the memory overhead constants of logarithmic data structures.
Continue learning
Previous: Bit manipulation tricks for CP