Fenwick Tree (Binary Indexed Tree)
The Intuition
The pattern is a structural compromise. A plain prefix-sum array answers prefix queries in O(1) but updates cost O(n). A balanced BST or segment tree gives O(log n) for both but with heavier code. A Fenwick tree splits the difference using one bit trick: each index i is responsible for a contiguous block of values whose length is the value of the lowest set bit of i.
That single rule generates the implicit tree. Index 1 covers position 1. Index 2 covers positions 1 to 2. Index 3 covers position 3. Index 4 covers positions 1 to 4, and so on. Walking up from any index by adding lowbit(i) jumps to the next block that contains it. Walking down by subtracting lowbit(i) lists the disjoint blocks whose union is the prefix 1..i.
The implementation is two short loops. Update walks upward adding delta at every block this index belongs to. Query walks downward summing the disjoint blocks that compose the prefix. Both touch O(log n) entries because each step strips a bit.
The pattern fits any associative, invertible operation. Sums and XOR are the common cases. Min and max work for prefix versions but not range queries because they are not invertible.
Once the structure is in place, several problems become a five-line wrapper. Counting inversions iterates the array in reverse, asks "how many smaller values have I already seen", and increments the rank's count. K-th order statistics with mutation use binary lifting on the BIT to find the smallest prefix whose sum reaches k. 2D Fenwick handles point updates and rectangle prefix sums on a grid by composing two 1D structures.
When the segment tree's lazy propagation is needed, Fenwick is not the right tool. For pure point-update plus prefix-or-range query, it is the lightest possible win.
Prefix sum with updates, range sum with updates, counting inversions, rank queries, dynamic order statistics, frequency counting at compressed coordinates.
- Range updates with lazy propagation (segment tree wins)
- Min/max range queries (operation is not invertible for arbitrary ranges)
- Static prefix sums with no updates (plain prefix array is simpler and faster)
Variations:
- Range update with point query: Use the difference-array trick. update(l, +d), update(r+1, -d), then prefixSum(i) gives the value at i.
- 2D Fenwick tree: O(log n × log m) for point updates and rectangle prefix sums.
- Binary lifting on BIT: Walk down powers of two from the highest bit to find the smallest prefix whose sum reaches a target. O(log n) instead of O(log^2 n).
- empty array (use n = 0; both loops do nothing)
- query at index 0 should return 0 (do not access bit[0])
- coordinate-compressed values but raw indices used by mistake
- delta math when caller supplies a "set to value" instead of "add delta"
Key Points
- •Each index i is responsible for a range of length lowbit(i) ending at i
- •lowbit(i) is i & -i (the lowest set bit isolated)
- •Update walks parents by i += lowbit(i); query walks ancestors by i -= lowbit(i)
- •1-indexed throughout to make the bit math clean
- •Lighter and easier to code than a segment tree when you only need prefix sums
Code Template
1 class FenwickTree:
2 def __init__(self, n):
3 # 1-indexed; index 0 is unused.
4 self.n = n
5 self.bit = [0] * (n + 1)
6
7 def update(self, i, delta):
8 """Add delta to the element at 1-indexed position i."""
9 while i <= self.n:
10 self.bit[i] += delta
11 i += i & -i
12
13 def prefix_sum(self, i):
14 """Sum of elements at indices 1..i."""
15 s = 0
16 while i > 0:
17 s += self.bit[i]
18 i -= i & -i
19 return s
20
21 def range_sum(self, l, r):
22 """Sum of elements at indices l..r (inclusive, 1-indexed)."""
23 return self.prefix_sum(r) - self.prefix_sum(l - 1)
24
25 @classmethod
26 def from_array(cls, arr):
27 """Build from a 0-indexed array in O(n)."""
28 ft = cls(len(arr))
29 # Internal 1-indexed storage; copy then propagate.
30 for i, v in enumerate(arr, start=1):
31 ft.bit[i] += v
32 parent = i + (i & -i)
33 if parent <= ft.n:
34 ft.bit[parent] += ft.bit[i]
35 return ft
36
37 def count_inversions(arr):
38 """Count pairs (i, j) with i < j and arr[i] > arr[j] using a Fenwick tree on ranks."""
39 sorted_unique = sorted(set(arr))
40 rank = {v: i + 1 for i, v in enumerate(sorted_unique)} # 1-indexed
41 ft = FenwickTree(len(sorted_unique))
42 inversions = 0
43 for v in reversed(arr):
44 inversions += ft.prefix_sum(rank[v] - 1)
45 ft.update(rank[v], 1)
46 return inversionsCommon Mistakes
- Using 0-indexed internal storage (the lowbit math breaks at 0)
- Forgetting that range_sum(l, r) is prefix(r) - prefix(l-1)
- Mixing the value to add (delta) with the new value (use delta = new - old)
- Coordinate-compressing values but updating with raw indices