DSA Fenwick Trees (Binary Indexed)
A Fenwick tree stores partial sums in a list where each index covers a range ending at itself. Updates climb upward through covering indices, and prefix queries descend by stripping the lowest set bit.
Lowbit decides the coverage
The lowbit of an index says how many values its cell covers. Index 8 covers eight values, while index 6 covers the two ending at 6.
for i in range(1, 13):
low = i & -i
print("index", i, "lowbit", low, "covers", low, "values ending at", i,
"starting at", i - low + 1)The stored cells
Building adds each value at its index and lets it climb. Cell 8 ends up holding the total of all eight values.
class Fenwick:
def __init__(self, values):
self.n = len(values)
self.tree = [0] * (self.n + 1)
for i, v in enumerate(values):
self.add(i, v)
def add(self, index, delta):
i = index + 1
steps = []
while i <= self.n:
self.tree[i] += delta
steps.append(i)
i += i & -i
return steps
def prefix(self, index):
i = index + 1
total = 0
steps = []
while i > 0:
total += self.tree[i]
steps.append(i)
i -= i & -i
return total, steps
def range_sum(self, left, right):
high, _ = self.prefix(right)
low, _ = self.prefix(left - 1) if left > 0 else (0, [])
return high - low
fw = Fenwick([3, 1, 4, 1, 5, 9, 2, 6])
print("tree cells 1..8:", fw.tree[1:])
print("prefix to index 5:", fw.prefix(5)[0])
print("range 2..5:", fw.range_sum(2, 5))Climbs and descents
A prefix query reads three cells to answer up to index 6. An update at index 2 also writes exactly three cells.
class Fenwick:
def __init__(self, values):
self.n = len(values)
self.tree = [0] * (self.n + 1)
for i, v in enumerate(values):
self.add(i, v)
def add(self, index, delta):
i = index + 1
steps = []
while i <= self.n:
self.tree[i] += delta
steps.append(i)
i += i & -i
return steps
def prefix(self, index):
i = index + 1
total = 0
steps = []
while i > 0:
total += self.tree[i]
steps.append(i)
i -= i & -i
return total, steps
def range_sum(self, left, right):
high, _ = self.prefix(right)
low, _ = self.prefix(left - 1) if left > 0 else (0, [])
return high - low
fw = Fenwick([3, 1, 4, 1, 5, 9, 2, 6])
total, steps = fw.prefix(6)
print("prefix to 6:", total, "cells read:", steps, "count:", len(steps))
steps = fw.add(2, 10)
print("update index 2 cells written:", steps, "count:", len(steps))
print("range 2..5 now:", fw.range_sum(2, 5))Example
class Fenwick:
def __init__(self, values):
self.n = len(values)
self.tree = [0] * (self.n + 1)
for i, v in enumerate(values):
self.add(i, v)
def add(self, index, delta):
i = index + 1
steps = []
while i <= self.n:
self.tree[i] += delta
steps.append(i)
i += i & -i
return steps
def prefix(self, index):
i = index + 1
total = 0
steps = []
while i > 0:
total += self.tree[i]
steps.append(i)
i -= i & -i
return total, steps
def range_sum(self, left, right):
high, _ = self.prefix(right)
low, _ = self.prefix(left - 1) if left > 0 else (0, [])
return high - low
values = [2, 5, 1, 7, 3, 8, 4, 6, 0, 9, 2, 5]
fw = Fenwick(values)
total_steps = 0
for index in (0, 4, 7, 11):
total, steps = fw.prefix(index)
total_steps += len(steps)
print("prefix to", index, "=", total, "steps:", len(steps),
"plain check:", total == sum(values[:index + 1]))
steps = fw.add(3, 10)
values[3] += 10
total_steps += len(steps)
print("update index 3 steps:", len(steps), steps)
print("range 2..8:", fw.range_sum(2, 8), "plain check:",
fw.range_sum(2, 8) == sum(values[2:9]))
steps = fw.add(10, -2)
values[10] -= 2
total_steps += len(steps)
print("update index 10 steps:", len(steps), steps)
print("range 0..11:", fw.range_sum(0, 11), "plain check:",
fw.range_sum(0, 11) == sum(values))
print("total steps counted:", total_steps)Key points
- Lowbit means the value of the lowest set bit in an index
- Index i stores the sum of the lowbit many values ending at position i
- An update adds the delta at index i, then jumps upward by the lowbit each step
- A prefix query reads index i, then drops the lowbit each step
- A range sum is the prefix up to the right end minus the prefix before the left end
In this example, a Fenwick tree over twelve values answers prefix sums in one or two steps each. Each answer is checked against a plain slice sum printed beside it. Two updates then climb two cells each, and every range sum still matches the plain list. Ten steps are counted across the four opening prefix queries and the two updates.
Note
a Fenwick tree needs no node objects, only one list of n plus one cells.
Try it Yourself
Edit the code, then press Run.
Running is simulated · Python Playground
Exercise
The descent for the prefix up to index 6 reads which cells?