Prefix sums answer range sum queries in O(1) after O(n) preprocessing — but what if the array updates between queries? A Fenwick tree (Binary Indexed Tree) handles both updates and queries in O(log n), using less code and memory than a segment tree.
The Prefix Sum Limitation
def build_prefix_sum(arr):
"""O(n) preprocessing, O(1) query, but O(n) update."""
prefix = [0] * (len(arr) + 1)
for i in range(len(arr)):
prefix[i + 1] = prefix[i] + arr[i]
return prefix
def range_sum(prefix, l, r):
"""Sum of arr[l..r] in O(1)."""
return prefix[r + 1] - prefix[l]
# Problem: updating arr[i] requires rebuilding the entire prefix array
# O(n) per update — too slow for real-time applicationsFenwick Tree: The Core Idea
A Fenwick tree stores partial sums at positions determined by the least significant set bit (LSB):
class FenwickTree:
def __init__(self, n):
self.n = n
self.tree = [0] * (n + 1)
def _lsb(self, x):
"""Least significant bit: isolates the lowest set bit."""
return x & (-x)
def update(self, i, delta):
"""Add delta to arr[i]. O(log n)."""
i += 1 # 1-indexed
while i <= self.n:
self.tree[i] += delta
i += self._lsb(i)
def query(self, i):
"""Prefix sum arr[0..i]. O(log n)."""
i += 1 # 1-indexed
s = 0
while i > 0:
s += self.tree[i]
i -= self._lsb(i)
return s
def range_sum(self, l, r):
"""Sum of arr[l..r]."""
return self.query(r) - (self.query(l - 1) if l > 0 else 0)How the LSB Path Works
def visualize_fenwick_path(tree_size: int = 16):
"""Show which positions are visited during prefix sum queries."""
for target in [1, 5, 7, 13, 16]:
path = []
i = target
while i > 0:
path.append(i)
i -= i & (-i)
print(f"query({target}): visits positions {path}")
# query(1): [1]
# query(5): [5, 4]
# query(7): [7, 6, 4]
# query(13): [13, 12, 8]
# query(16): [16]def visualize_fenwick_tree(n: int = 16):
"""Show what each position in the Fenwick tree stores."""
tree = [0] * (n + 1)
arr = list(range(1, n + 1)) # arr[i] = i+1 for visualization
for i in range(n):
val = arr[i]
pos = i + 1
while pos <= n:
tree[pos] += val
pos += pos & (-pos)
for i in range(1, n + 1):
lsb = i & (-i)
print(f"tree[{i}] = {tree[i]} (stores arr[{i-lsb}..{i-1}] sum)")
# tree[1] = 1 (stores arr[0..0])
# tree[2] = 3 (stores arr[0..1])
# tree[3] = 3 (stores arr[2..2])
# tree[4] = 10 (stores arr[0..3])
# tree[5] = 5 (stores arr[4..4])
# tree[6] = 11 (stores arr[4..5])
# tree[7] = 7 (stores arr[6..6])
# tree[8] = 36 (stores arr[0..7])Range Updates with Difference Arrays
Fenwick trees can also support range updates (add value to all elements in [l, r]):
class FenwickRangeUpdate:
"""Fenwick tree supporting range updates and point queries."""
def __init__(self, n):
self.n = n
self.tree = [0] * (n + 1)
def _update(self, i, delta):
i += 1
while i <= self.n:
self.tree[i] += delta
i += i & (-i)
def range_add(self, l, r, val):
"""Add val to all elements in [l, r]."""
self._update(l, val)
self._update(r + 1, -val)
def point_query(self, i):
"""Get value at index i."""
s = 0
i += 1
while i > 0:
s += self.tree[i]
i -= i & (-i)
return s
# Usage:
ft = FenwickRangeUpdate(10)
ft.range_add(2, 7, 5) # add 5 to indices 2..7
ft.range_add(4, 5, 3) # add 3 to indices 4..5
# point_query(4) → 8 (5 + 3)
# point_query(6) → 5 (only the first update)tradeoff / Fenwick Tree vs Segment Tree
For most practical applications involving range sums (analytics, cumulative statistics, real-time counters), Fenwick trees are the better choice. They use less memory and have smaller constant factors than segment trees.
Fenwick trees are preferred when you only need sum queries and updates. Segment trees are required for more complex queries like range minimum, range GCD, or arbitrary combining operations.
Synthesis
Fenwick trees achieve O(log n) updates and queries with minimal code by exploiting the binary representation of array indices. The LSB operation determines which positions store partial sums, enabling efficient traversal. For range updates, the difference array technique extends Fenwick trees to handle bulk modifications. This is the go-to data structure for online prefix sum problems.