Released · improving
Algorithm
A segment tree answers range sum and minimum queries and applies point updates in O(log n); the Fenwick tree is its lighter cousin for sums.
A segment tree is a binary tree that stores a summary, such as a sum, minimum, or maximum, for every range obtained by repeatedly halving an array. The root covers the whole array, each leaf covers a single element, and every internal node combines its two children. Any question about a contiguous range can then be answered by combining a handful of nodes.
Prefix sums answer range sums in O(1) but need O(n) to absorb a single change, while a plain array updates instantly but needs O(n) per query. A segment tree handles both point updates and range queries in O(log n), which makes it the right tool when values keep changing and range questions keep arriving. With lazy propagation it also supports range updates, such as adding a value to an entire range, in O(log n).
Start by understanding where prefix sums fall short, then draw a small tree by hand and trace which nodes a query and an update touch. Next, write the short iterative implementation and a Fenwick tree yourself, and practice on classic problems such as range minimum, counting inversions, and range add with range sum until the patterns feel natural.
Each node owns one range of the array and stores its sum or minimum; any associative operation with an identity element fits the same structure.
Changing an element recomputes one leaf-to-root path, and a range query combines at most two nodes per level.
A range update leaves a note on the nodes that cover it and passes the note to children only when an operation must descend, keeping it O(log n).
For invertible operations such as sums, a Fenwick tree (BIT) reaches the same complexity with an n + 1 array and a few short loops.
An iterative segment tree: the elements sit in the second half of a 2n array and each earlier slot holds the sum of its two children. update climbs from the leaf to the root recomputing sums, and query climbs from both ends of the half-open range [left, right), adding only the boundary nodes. Running it prints 26, 17, and 28.
segment_tree.py
class SegmentTree:
"""Iterative segment tree: point update and range sum in O(log n)."""
def __init__(self, values):
self.n = len(values)
self.tree = [0] * self.n + list(values)
for i in range(self.n - 1, 0, -1):
self.tree[i] = self.tree[2 * i] + self.tree[2 * i + 1]
def update(self, index, value):
i = index + self.n
self.tree[i] = value
while i > 1:
i //= 2
self.tree[i] = self.tree[2 * i] + self.tree[2 * i + 1]
def query(self, left, right):
"""Sum of values[left:right] (half-open range)."""
total = 0
lo, hi = left + self.n, right + self.n
while lo < hi:
if lo & 1:
total += self.tree[lo]
lo += 1
if hi & 1:
hi -= 1
total += self.tree[hi]
lo //= 2
hi //= 2
return total
if __name__ == "__main__":
tree = SegmentTree([5, 3, 7, 9, 6, 4, 1, 2])
print(tree.query(2, 6)) # 7 + 9 + 6 + 4 = 26
tree.update(3, 0)
print(tree.query(2, 6)) # 7 + 0 + 6 + 4 = 17
print(tree.query(0, 8)) # 28
python segment_tree.pySix chapters that take you from installation to the core ideas of Segment trees.
Ask questions, share experience and trade opinions about Segment trees.
No discussions yet. Start the first one.
0 comments
Sign in · Sign in to leave a comment.
Be the first to comment.