Data Structures · Lesson 16 of 16
Segment Trees and Fenwick Trees
Answer range sum and range minimum queries with updates in O(log n) using prefix sums, Fenwick trees (binary indexed trees) and segment trees in Python.
- Advanced
- 18 min read
- 4 objectives
Before this lessonLesson 15: Union-Find (Disjoint Set Union)
What you will learn
- See why prefix sums break when data changes
- Implement a Fenwick tree for point updates and prefix sums
- Implement a segment tree for any associative range query
- Choose between the two using a complexity table
Your Progress
0 of 16 lessons 0%
- Lessons0 / 16
- Completed0
- Est. time left~ 4 hours
Create a free account to keep your progress on every device.
Tip: pressing Next marks this lesson complete automatically.
Imagine a dashboard showing sales per day. Users ask "total sales from day 30 to day 90" thousands of times a second, while new orders keep changing individual days. Summing the range each time is O(n) per query. Precomputing prefix sums makes queries O(1), but then a single update costs O(n). This lesson covers two structures that make both operations O(log n): the Fenwick tree and the segment tree.
Starting point: prefix sums
A prefix sum array stores prefix[i] = a[0] + ... + a[i-1]. The sum of a[l..r] is then prefix[r+1] - prefix[l], one subtraction. This is the best tool when the data never changes.
from itertools import accumulate
sales = [5, 3, 7, 2, 6, 1, 4]
prefix = [0] + list(accumulate(sales))
print(prefix)
def range_sum(l, r): # inclusive
return prefix[r + 1] - prefix[l]
print(range_sum(1, 3), range_sum(0, 6))[0, 5, 8, 15, 17, 23, 24, 28] 12 28
The problem: if sales[1] changes, every prefix value after it is wrong and must be rebuilt, which is O(n). With many updates and many queries, that is too slow.
Fenwick tree (binary indexed tree)
A Fenwick tree, or binary indexed tree (BIT), is an array where each slot stores the sum of a block of elements. The size of the block is decided by the lowest set bit of the index, i & -i. Using 1-based indices:
- Slot 4 (binary 100) covers 4 elements: 1 to 4.
- Slot 6 (binary 110) covers 2 elements: 5 to 6.
- Slot 7 (binary 111) covers 1 element: 7.
A prefix sum up to i adds a few blocks, jumping with i -= i & -i. An update at i fixes every block that contains i, jumping with i += i & -i. Each loop runs at most log2 n times.
class Fenwick:
def __init__(self, n):
self.n = n
self.tree = [0] * (n + 1) # index 0 unused
def add(self, i, delta): # i is 0-based for callers
i += 1
while i <= self.n:
self.tree[i] += delta
i += i & -i
def prefix(self, i): # sum of a[0..i-1]
total = 0
while i > 0:
total += self.tree[i]
i -= i & -i
return total
def range_sum(self, l, r): # inclusive, 0-based
return self.prefix(r + 1) - self.prefix(l)
sales = [5, 3, 7, 2, 6, 1, 4]
fw = Fenwick(len(sales))
for i, v in enumerate(sales):
fw.add(i, v)
print(fw.range_sum(1, 3))
fw.add(1, 10) # day 1 gets 10 more sales
print(fw.range_sum(1, 3), fw.range_sum(0, 6))12 22 38
The Fenwick tree is tiny (one array, about 15 lines) and fast. Its limitation is that it relies on subtraction to turn two prefix sums into a range, so it naturally handles sums and counts but not range minimum or maximum.
for i in [4, 6, 7, 12]:
low = i & -i
print(f"slot {i:>2} ({i:04b}) covers {low} element(s): {i - low + 1}..{i}")slot 4 (0100) covers 4 element(s): 1..4 slot 6 (0110) covers 2 element(s): 5..6 slot 7 (0111) covers 1 element(s): 7..7 slot 12 (1100) covers 4 element(s): 9..12
Segment tree
A segment tree is a binary tree where each node stores the answer for a range: the root covers the whole array, its children cover the left and right halves, and leaves cover single elements. It works for any associative operation: sum, min, max, gcd, even "count of values above a threshold". An iterative version stores it in an array of size 2n, with leaves at positions n to 2n - 1 and node i's children at 2i and 2i + 1.
class SegmentTree:
def __init__(self, data, op, identity):
self.n = len(data)
self.op, self.identity = op, identity
self.t = [identity] * self.n + list(data)
for i in range(self.n - 1, 0, -1):
self.t[i] = op(self.t[2 * i], self.t[2 * i + 1])
def update(self, i, value): # set a[i] = value
i += self.n
self.t[i] = value
while i > 1:
i //= 2
self.t[i] = self.op(self.t[2 * i], self.t[2 * i + 1])
def query(self, l, r): # inclusive l..r
res_left = res_right = self.identity
l += self.n
r += self.n + 1
while l < r:
if l & 1:
res_left = self.op(res_left, self.t[l]); l += 1
if r & 1:
r -= 1; res_right = self.op(self.t[r], res_right)
l //= 2
r //= 2
return self.op(res_left, res_right)
temps = [21, 18, 25, 17, 30, 22, 19]
mins = SegmentTree(temps, min, float("inf"))
sums = SegmentTree(temps, lambda a, b: a + b, 0)
print(mins.query(0, 2), mins.query(2, 5), sums.query(0, 6))
mins.update(3, 26)
print(mins.query(2, 5))18 17 152 22
The same class answered range minimum and range sum just by passing a different operation and its identity value (the value that changes nothing: 0 for sum, infinity for min). A query touches at most about 2 log2 n nodes, and an update walks from one leaf to the root.
Checking against brute force
Tricky index code deserves a test. Compare your structure with the obvious slow answer on random data; this catches off-by-one bugs quickly.
import random
class SegmentTree:
def __init__(self, data):
self.n = len(data)
self.t = [0] * self.n + list(data)
for i in range(self.n - 1, 0, -1):
self.t[i] = max(self.t[2 * i], self.t[2 * i + 1])
def update(self, i, v):
i += self.n; self.t[i] = v
while i > 1:
i //= 2; self.t[i] = max(self.t[2 * i], self.t[2 * i + 1])
def query(self, l, r):
best = float("-inf"); l += self.n; r += self.n + 1
while l < r:
if l & 1: best = max(best, self.t[l]); l += 1
if r & 1: r -= 1; best = max(best, self.t[r])
l //= 2; r //= 2
return best
random.seed(1)
data = [random.randint(0, 100) for _ in range(50)]
st = SegmentTree(data)
ok = True
for _ in range(1000):
if random.random() < 0.3:
i, v = random.randrange(50), random.randint(0, 100)
data[i] = v; st.update(i, v)
else:
l = random.randrange(50); r = random.randrange(l, 50)
ok &= st.query(l, r) == max(data[l:r + 1])
print("all queries match:", ok)all queries match: True
Going further
- Range updates ("add 5 to every day from 10 to 20") use a segment tree with lazy propagation, which postpones updates to children until they are needed. It keeps both operations O(log n).
- A Fenwick tree over a difference array supports range add with point query using the same 15 lines.
- Real uses include leaderboards (rank = count of scores above you), time-series dashboards, competitive programming and computational geometry.
Complexity
Plain array Prefix sums Fenwick tree Segment tree
build O(1) O(n) O(n log n)* O(n)
point update O(1) O(n) O(log n) O(log n)
range sum O(n) O(1) O(log n) O(log n)
range min/max O(n) not supported not supported** O(log n)
range update O(n) O(n) O(log n)*** O(log n) with lazy
memory n n + 1 n + 1 2n (or 4n recursive)
* O(n) with a linear build trick
** only for special cases such as values that only grow
*** range add with point query, via a difference arrayRule of thumb: if data never changes, use prefix sums. If you need sums or counts with updates, a Fenwick tree is smallest and simplest. If you need min, max or another operation, or range updates, reach for a segment tree.
Recap
- Prefix sums give O(1) range sums but O(n) updates.
- A Fenwick tree uses the lowest set bit (
i & -i) to get O(log n) updates and prefix sums in one small array. - A segment tree stores range answers in a binary tree and supports any associative operation in O(log n).
- Use 1-based indices for Fenwick trees and identity values for segment trees.
- Test index-heavy structures against brute force on random data.
# Write your solution here
Finished reading? Mark this lesson complete to track your progress.