DSA Segment Trees
A segment tree is a binary tree where each node stores the answer for one range. A query or an update visits only the nodes on the paths it needs.
The tree as an array
The tree lives in a list where node i keeps its children at 2i and 2i plus 1. The root at index 1 holds the total of all eight values.
class SegTree:
def __init__(self, values):
self.n = len(values)
self.tree = [0] * (4 * self.n)
self.visited = 0
self.build(1, 0, self.n - 1, values)
def build(self, node, left, right, values):
if left == right:
self.tree[node] = values[left]
return
mid = (left + right) // 2
self.build(node * 2, left, mid, values)
self.build(node * 2 + 1, mid + 1, right, values)
self.tree[node] = self.tree[node * 2] + self.tree[node * 2 + 1]
def query(self, node, left, right, ql, qr):
self.visited += 1
if ql <= left and right <= qr:
return self.tree[node]
mid = (left + right) // 2
total = 0
if ql <= mid:
total += self.query(node * 2, left, mid, ql, qr)
if qr > mid:
total += self.query(node * 2 + 1, mid + 1, right, ql, qr)
return total
def sum(self, ql, qr):
self.visited = 0
return self.query(1, 0, self.n - 1, ql, qr)
def update(self, node, left, right, index, value):
self.visited += 1
if left == right:
self.tree[node] = value
return
mid = (left + right) // 2
if index <= mid:
self.update(node * 2, left, mid, index, value)
else:
self.update(node * 2 + 1, mid + 1, right, index, value)
self.tree[node] = self.tree[node * 2] + self.tree[node * 2 + 1]
def set(self, index, value):
self.visited = 0
self.update(1, 0, self.n - 1, index, value)
seg = SegTree([3, 1, 4, 1, 5, 9, 2, 6])
print("nodes 1..15:", seg.tree[1:16])
print("root holds:", seg.tree[1])Queries count their visits
A full-range query stops at the root in one visit. A partial query descends only toward the ranges it overlaps.
class SegTree:
def __init__(self, values):
self.n = len(values)
self.tree = [0] * (4 * self.n)
self.visited = 0
self.build(1, 0, self.n - 1, values)
def build(self, node, left, right, values):
if left == right:
self.tree[node] = values[left]
return
mid = (left + right) // 2
self.build(node * 2, left, mid, values)
self.build(node * 2 + 1, mid + 1, right, values)
self.tree[node] = self.tree[node * 2] + self.tree[node * 2 + 1]
def query(self, node, left, right, ql, qr):
self.visited += 1
if ql <= left and right <= qr:
return self.tree[node]
mid = (left + right) // 2
total = 0
if ql <= mid:
total += self.query(node * 2, left, mid, ql, qr)
if qr > mid:
total += self.query(node * 2 + 1, mid + 1, right, ql, qr)
return total
def sum(self, ql, qr):
self.visited = 0
return self.query(1, 0, self.n - 1, ql, qr)
def update(self, node, left, right, index, value):
self.visited += 1
if left == right:
self.tree[node] = value
return
mid = (left + right) // 2
if index <= mid:
self.update(node * 2, left, mid, index, value)
else:
self.update(node * 2 + 1, mid + 1, right, index, value)
self.tree[node] = self.tree[node * 2] + self.tree[node * 2 + 1]
def set(self, index, value):
self.visited = 0
self.update(1, 0, self.n - 1, index, value)
seg = SegTree([3, 1, 4, 1, 5, 9, 2, 6])
print("sum 0..7:", seg.sum(0, 7), "visited:", seg.visited)
print("sum 2..5:", seg.sum(2, 5), "visited:", seg.visited)
print("sum 3..3:", seg.sum(3, 3), "visited:", seg.visited)An update climbs back up
Setting index 3 to 10 rewrites its leaf. Every ancestor on the climb refreshes its stored sum.
class SegTree:
def __init__(self, values):
self.n = len(values)
self.tree = [0] * (4 * self.n)
self.visited = 0
self.build(1, 0, self.n - 1, values)
def build(self, node, left, right, values):
if left == right:
self.tree[node] = values[left]
return
mid = (left + right) // 2
self.build(node * 2, left, mid, values)
self.build(node * 2 + 1, mid + 1, right, values)
self.tree[node] = self.tree[node * 2] + self.tree[node * 2 + 1]
def query(self, node, left, right, ql, qr):
self.visited += 1
if ql <= left and right <= qr:
return self.tree[node]
mid = (left + right) // 2
total = 0
if ql <= mid:
total += self.query(node * 2, left, mid, ql, qr)
if qr > mid:
total += self.query(node * 2 + 1, mid + 1, right, ql, qr)
return total
def sum(self, ql, qr):
self.visited = 0
return self.query(1, 0, self.n - 1, ql, qr)
def update(self, node, left, right, index, value):
self.visited += 1
if left == right:
self.tree[node] = value
return
mid = (left + right) // 2
if index <= mid:
self.update(node * 2, left, mid, index, value)
else:
self.update(node * 2 + 1, mid + 1, right, index, value)
self.tree[node] = self.tree[node * 2] + self.tree[node * 2 + 1]
def set(self, index, value):
self.visited = 0
self.update(1, 0, self.n - 1, index, value)
seg = SegTree([3, 1, 4, 1, 5, 9, 2, 6])
seg.set(3, 10)
print("update visited:", seg.visited)
print("root holds:", seg.tree[1])
print("sum 2..5:", seg.sum(2, 5), "visited:", seg.visited)Example
class SegTree:
def __init__(self, values):
self.n = len(values)
self.tree = [0] * (4 * self.n)
self.visited = 0
self.build(1, 0, self.n - 1, values)
def build(self, node, left, right, values):
if left == right:
self.tree[node] = values[left]
return
mid = (left + right) // 2
self.build(node * 2, left, mid, values)
self.build(node * 2 + 1, mid + 1, right, values)
self.tree[node] = self.tree[node * 2] + self.tree[node * 2 + 1]
def query(self, node, left, right, ql, qr):
self.visited += 1
if ql <= left and right <= qr:
return self.tree[node]
mid = (left + right) // 2
total = 0
if ql <= mid:
total += self.query(node * 2, left, mid, ql, qr)
if qr > mid:
total += self.query(node * 2 + 1, mid + 1, right, ql, qr)
return total
def sum(self, ql, qr):
self.visited = 0
return self.query(1, 0, self.n - 1, ql, qr)
def update(self, node, left, right, index, value):
self.visited += 1
if left == right:
self.tree[node] = value
return
mid = (left + right) // 2
if index <= mid:
self.update(node * 2, left, mid, index, value)
else:
self.update(node * 2 + 1, mid + 1, right, index, value)
self.tree[node] = self.tree[node * 2] + self.tree[node * 2 + 1]
def set(self, index, value):
self.visited = 0
self.update(1, 0, self.n - 1, index, value)
values = [5, 2, 7, 1, 8, 3, 6, 4, 9, 0, 2, 5, 1, 7, 3, 6]
seg = SegTree(values)
print("total:", seg.tree[1])
for ql, qr in [(0, 15), (3, 10), (5, 5), (8, 15), (0, 3)]:
got = seg.sum(ql, qr)
print("sum", ql, "..", qr, "=", got, "visited:", seg.visited,
"plain check:", got == sum(values[ql:qr + 1]))
seg.set(9, 12)
values[9] = 12
print("after set index 9 to 12, update visited:", seg.visited)
print("total:", seg.tree[1])
print("sum 8..15:", seg.sum(8, 15), "visited:", seg.visited,
"plain check:", seg.tree[1] == sum(values))Key points
- Each leaf holds one element and each internal node holds the sum of its range
- The root node holds the answer for the whole list
- A range query combines the stored sums of the nodes that cover the range
- A point update rewrites one leaf and refreshes every ancestor above it
- Each level of the tree adds at most a few visited nodes to one operation
In this example, a segment tree over 16 values answers five range sums. Every answer matches the plain slice sum printed beside it. The full-range query visits one node, while the widest partial query visits eleven. One point update visits five nodes, one per level, and the root total rises from 69 to 81.
Note
this lesson builds sums, but a node can hold any combinable answer, like a minimum.
Try it Yourself
Edit the code, then press Run.
Running is simulated · Python Playground
Exercise
A segment tree query sums range 2..5 without visiting every leaf in it. Why?