Fenwick Tree: Binary Indexed Tree Implementation
Consider a common scenario: you have an array of numbers and need to repeatedly compute prefix sums while also updating individual elements. This appears in countless applications—tracking cumulative...
Key Insights
- Fenwick Trees exploit binary representation of indices to achieve O(log n) updates and queries, making them ideal for dynamic prefix sum problems where both operations need to be fast.
- The lowest set bit (LSB) operation
i & (-i)is the foundation of all Fenwick Tree operations, determining which ranges each index is responsible for and how to traverse the tree. - While segment trees are more flexible, Fenwick Trees use half the memory, have smaller constants, and are significantly easier to implement—making them the preferred choice when you only need prefix sums and point updates.
The Problem with Naive Approaches
Consider a common scenario: you have an array of numbers and need to repeatedly compute prefix sums while also updating individual elements. This appears in countless applications—tracking cumulative sales, maintaining leaderboard rankings, or computing running statistics.
With a plain array, you face an uncomfortable tradeoff. Store the raw values and queries take O(n) time. Precompute prefix sums and updates become O(n) because you need to modify every subsequent sum. When you’re handling millions of operations, neither approach scales.
Fenwick Trees, also called Binary Indexed Trees (BIT), solve this elegantly. Both operations run in O(log n) time using a surprisingly simple data structure. The implementation fits in about 20 lines of code, yet the underlying bit manipulation is genuinely clever.
Core Concept: Binary Index Magic
The brilliance of Fenwick Trees lies in how they use binary representations of indices to implicitly define a tree structure. Every index in the tree is responsible for a specific range of the original array, and that range is determined entirely by the index’s lowest set bit.
Here’s the key operation that makes everything work:
def lowest_set_bit(i):
"""Returns the lowest set bit of i.
Examples:
12 (1100) -> 4 (0100)
6 (0110) -> 2 (0010)
8 (1000) -> 8 (1000)
7 (0111) -> 1 (0001)
"""
return i & (-i)
This works because of two’s complement representation. Negating a number flips all bits and adds one, which means -i shares only the lowest set bit with i. The bitwise AND isolates exactly that bit.
The lowest set bit determines how many elements each index is responsible for. Index 8 (binary 1000) has LSB of 8, so it covers 8 elements. Index 6 (binary 0110) has LSB of 2, so it covers 2 elements. Index 7 (binary 0111) has LSB of 1, covering just 1 element.
Tree Structure & Index Mapping
A Fenwick Tree is stored as a 1-indexed array where each position stores the sum of a specific range. The range that index i covers is [i - LSB(i) + 1, i].
Let’s trace through what each index stores for an 8-element array:
def show_responsibilities(n):
"""Display what range each Fenwick Tree index covers."""
print("Index | Binary | LSB | Covers Range | Length")
print("-" * 50)
for i in range(1, n + 1):
lsb = i & (-i)
start = i - lsb + 1
print(f" {i} | {i:04b} | {lsb} | [{start}, {i}] | {lsb}")
# Output for n=8:
# Index | Binary | LSB | Covers Range | Length
# --------------------------------------------------
# 1 | 0001 | 1 | [1, 1] | 1
# 2 | 0010 | 2 | [1, 2] | 2
# 3 | 0011 | 1 | [3, 3] | 1
# 4 | 0100 | 4 | [1, 4] | 4
# 5 | 0101 | 1 | [5, 5] | 1
# 6 | 0110 | 2 | [5, 6] | 2
# 7 | 0111 | 1 | [7, 7] | 1
# 8 | 1000 | 8 | [1, 8] | 8
Notice the pattern: indices with larger LSB values cover wider ranges. Index 8 alone covers the entire array. This hierarchical structure is what enables logarithmic operations.
Update Operation
When you update a value at position i, you need to modify every Fenwick Tree index whose range includes position i. You find these indices by repeatedly adding the LSB to the current index.
def update(tree, i, delta):
"""Add delta to position i (1-indexed).
Propagates the change to all indices responsible for position i.
Each iteration moves to the next index that covers this position.
"""
n = len(tree) - 1 # tree[0] is unused
while i <= n:
tree[i] += delta
# Move to next responsible index by adding LSB
i += i & (-i)
# Trace for update at position 3:
# i=3 (0011): update tree[3], add LSB(3)=1 -> i=4
# i=4 (0100): update tree[4], add LSB(4)=4 -> i=8
# i=8 (1000): update tree[8], add LSB(8)=8 -> i=16 (done)
The update touches at most O(log n) indices because each step increases the position of the lowest set bit, and there are only log n bit positions.
Prefix Sum Query
Querying the prefix sum up to index i works in reverse: you accumulate values while removing the LSB to traverse to all contributing nodes.
def prefix_sum(tree, i):
"""Return sum of elements from index 1 to i (inclusive).
Accumulates values by traversing to all nodes that contribute
to the prefix sum at position i.
"""
total = 0
while i > 0:
total += tree[i]
# Move to previous contributing index by removing LSB
i -= i & (-i)
return total
# Trace for query at position 7:
# i=7 (0111): add tree[7], subtract LSB(7)=1 -> i=6
# i=6 (0110): add tree[6], subtract LSB(6)=2 -> i=4
# i=4 (0100): add tree[4], subtract LSB(4)=4 -> i=0 (done)
# Result: tree[7] + tree[6] + tree[4]
For range queries, use the prefix sum identity: sum(l, r) = prefix_sum(r) - prefix_sum(l - 1).
def range_sum(tree, left, right):
"""Return sum of elements from left to right (inclusive, 1-indexed)."""
return prefix_sum(tree, right) - prefix_sum(tree, left - 1)
Complete Implementation
Here’s a production-ready implementation with proper initialization and a clean interface:
class FenwickTree:
"""Binary Indexed Tree for efficient prefix sums and point updates.
Both operations run in O(log n) time with O(n) space.
Uses 1-based indexing internally.
"""
def __init__(self, data):
"""Initialize from an iterable of values.
Args:
data: Initial values (0-indexed input, converted to 1-indexed)
Time: O(n)
"""
self.n = len(data)
self.tree = [0] * (self.n + 1)
# Build tree in O(n) using the "propagate up" trick
for i, val in enumerate(data, start=1):
self.tree[i] += val
parent = i + (i & (-i))
if parent <= self.n:
self.tree[parent] += self.tree[i]
def update(self, i, delta):
"""Add delta to element at index i (0-indexed input).
Time: O(log n)
"""
i += 1 # Convert to 1-indexed
while i <= self.n:
self.tree[i] += delta
i += i & (-i)
def set(self, i, value):
"""Set element at index i to value (0-indexed input).
Time: O(log n)
"""
current = self.range_query(i, i)
self.update(i, value - current)
def prefix_query(self, i):
"""Return sum of elements from index 0 to i (inclusive, 0-indexed).
Time: O(log n)
"""
i += 1 # Convert to 1-indexed
total = 0
while i > 0:
total += self.tree[i]
i -= i & (-i)
return total
def range_query(self, left, right):
"""Return sum of elements from left to right (inclusive, 0-indexed).
Time: O(log n)
"""
if left == 0:
return self.prefix_query(right)
return self.prefix_query(right) - self.prefix_query(left - 1)
The constructor uses an O(n) building technique instead of O(n log n) individual updates. Each element propagates its value directly to its parent, which is found by adding the LSB.
Complexity Analysis & When to Use
Time Complexity:
- Update: O(log n)
- Prefix query: O(log n)
- Range query: O(log n)
- Construction: O(n)
Space Complexity: O(n) — just one array of size n+1.
Fenwick Tree vs. Segment Tree:
Segment trees are more powerful. They support range updates, arbitrary range operations (min, max, GCD), and lazy propagation. But that power comes with costs: 2-4x memory usage, more complex implementation, and larger constants.
Choose Fenwick Trees when you only need prefix sums and point updates. They’re faster in practice, easier to debug, and the implementation is nearly impossible to get wrong once you understand it.
Fenwick Tree vs. Prefix Sum Array:
Prefix sum arrays give O(1) queries but O(n) updates. If your data is static, use prefix sums. If you have frequent updates, use Fenwick Trees.
Practical Application: Counting Inversions
A classic application is counting inversions in an array—pairs where a larger element appears before a smaller one. This is useful for measuring how “unsorted” data is.
def count_inversions(arr):
"""Count pairs (i, j) where i < j but arr[i] > arr[j].
Uses coordinate compression + Fenwick Tree.
Time: O(n log n)
"""
# Coordinate compression: map values to ranks 0 to n-1
sorted_unique = sorted(set(arr))
rank = {v: i for i, v in enumerate(sorted_unique)}
n = len(sorted_unique)
tree = FenwickTree([0] * n)
inversions = 0
# Process elements right to left
for val in reversed(arr):
r = rank[val]
# Count elements smaller than current that we've seen
# (they appear to the right but are smaller = inversions)
if r > 0:
inversions += tree.prefix_query(r - 1)
# Mark this element as seen
tree.update(r, 1)
return inversions
# Example
arr = [3, 1, 2]
print(count_inversions(arr)) # Output: 2 (pairs: (3,1), (3,2))
The algorithm processes elements from right to left, using the Fenwick Tree as a frequency table. For each element, we count how many smaller elements we’ve already seen (those are inversions), then mark the current element as seen.
Fenwick Trees are one of those data structures that seem magical until you understand the bit manipulation. Once it clicks, you’ll find yourself reaching for them whenever you need fast cumulative statistics on dynamic data. The implementation is compact enough to write from memory in competitive programming, yet robust enough for production systems handling millions of updates per second.