Fenwick tree (BIT)
Overview
A data structure that can efficiently update elements and calculate prefix sums in a table of numbers, using bitwise tricks.
It requires exactly O(N) space and has extremely small constant factors, making it faster and much easier to code than a Segment Tree (for sum queries).
Where used: Inversion counting, Frequency tables in compression algorithms (Arithmetic coding)
Why it exists
Problem: Segment Trees solve Mutable Range Queries in O(log n), but they are heavily verbose to code and require 4N space. We want a lighter, faster array structure that does the same thing.
Naive approach: Use a Segment Tree, writing 30 lines of recursive code.
Better idea: Use the bits of the array indices themselves to represent segment bounds. A Fenwick Tree (Binary Indexed Tree) stores partial sums in exactly N space, and updates/queries take just a 3-line while loop using bitwise operations.
Why learn this
- It is the fastest way to implement a mutable prefix sum in a competitive programming context.
- It demonstrates a brilliant use of two's complement bit manipulation.
Mental model
Every number can be decomposed into a sum of powers of two (e.g., 7 = 4 + 2 + 1). A Fenwick tree decomposes a range `[1, 7]` into 3 pre-calculated segments of lengths 4, 2, and 1.
A 1-indexed array where index `i` stores the sum of `[i - LSB(i) + 1, i]`. LSB is the Least Significant Bit. To query the prefix sum up to `i`, we repeatedly subtract the LSB to jump backwards. To update `i`, we repeatedly add the LSB to jump forwards and update all segments that cover `i`.
Repeated decision: Querying? Strip off the lowest bit to find the next segment. Updating? Add the lowest bit to find the next parent segment.
Deep dive
The magic of a Fenwick Tree relies entirely on the bitwise isolation trick: `i & (-i)`. In two's complement arithmetic, `-i` inverts all bits and adds 1. When you AND that with `i`, it extracts the Least Significant 1-Bit (LSB). For example, if `i = 10` (binary `1010`), the LSB is `2` (`0010`).
The tree is just a 1-indexed array of size `N + 1`. The value at `tree[i]` stores the sum of a specific block of elements. The size of this block is exactly `LSB(i)`. So `tree[10]` stores the sum of a block of size 2, specifically the original array elements at index 9 and 10.
**To query the prefix sum up to index `i`:** You add `tree[i]` to a running total, then strip the LSB from `i` (`i -= i & (-i)`). This jumps backwards to the previous adjacent block. You repeat until `i == 0`.
**To update an element at index `i` by `val`:** You add `val` to `tree[i]`, then ADD the LSB to `i` (`i += i & (-i)`). This jumps forwards to the next larger block that completely contains the current block, and you update that too. Repeat until `i > N`.
Both operations traverse at most the number of bits in `N`, so they run in `O(log N)` time.
Key points
- Complexity: Time is O(log N) for point update and prefix query. Space is O(N). Construction can be O(N) but is usually done via N point-updates in O(N log N).
- 1-Indexed Requirement: Fenwick Trees absolutely MUST be 1-indexed. If `i = 0`, `i & (-i)` is 0, and `i += 0` causes an infinite loop.
Pattern: Fenwick Tree / BIT
Recognition cues:
- Mutable Prefix Sums
- Counting inversions in an array
Failure signals
- The problem requires Range Updates and Range Queries (Fenwick can do this, but it requires two synchronized trees, which is very complex).
Engineering examples
Data compression
Arithmetic coding needs to dynamically maintain cumulative frequencies of characters.
Fenwick Trees provide exactly this cumulative frequency distribution with fast updates.
When not to use
- Non-invertible operations: It natively only supports operations where `Query(L, R)` can be derived from `Prefix(R)` inverse `Prefix(L-1)`. For Min/Max, you should use a Segment Tree.
Common mistakes
- Using 0-based indexing: If you try to update or query index 0, the bitwise LSB operation fails and loops infinitely. Always offset your queries by +1.
- Using it for Range Minimum Query (RMQ): Fenwick trees rely on the fact that `Sum(L, R) = Sum(R) - Sum(L-1)`. This requires an inverse operation (subtraction). Min/Max operations do not have an inverse. While RMQ Fenwick Trees are technically possible, they are highly restricted; use a Segment Tree for Min/Max.
Recall questions
- What bitwise trick is used to isolate the Least Significant 1-Bit in a Fenwick Tree?
- Why must a Fenwick tree be 1-indexed?
- Why is a Fenwick Tree better than a Segment Tree for simple sum queries?
Understanding checks
If you query a Fenwick tree at index 7 (binary `0111`), what indices are accessed in the tree array?
Indices 7, 6, and 4.
7 is `0111`. Strip LSB: `0110` (6). Strip LSB: `0100` (4). Strip LSB: `0000` (0, stop). It sums three blocks.
What is the value of `i & (-i)` for `i = 12`?
4.
12 in binary is `1100`. The lowest set bit is the `100` bit, which has a decimal value of 4.
Questions & answers
Count Inversions in an Array
Iterate backwards. Ask a BIT 'how many numbers smaller than me have we seen so far?', then update the BIT to include yourself.
Approach: Coordinate compression is usually required if the numbers are large, because the BIT array size is proportional to the maximum value in the array.
Practice tasks
Range Sum Query - Mutable
Implement a class `NumArray` that supports updating an element and calculating the sum of elements in `[left, right]`. Try doing it with a Fenwick Tree this time.
Continue learning
Previous: Bitwise operators