Segment Tree

A segment tree stores information about intervals in a tree-shaped structure.

It supports efficient range queries and updates for many associative operations.

Core Idea

Each node represents a segment of the array. Parent nodes combine information from child segments. A query decomposes the requested range into stored segments.

For many operations, query and point update are O(log n).

Python Example

class SegmentTree:
    def __init__(self, values):
        self.n = 1
        while self.n < len(values):
            self.n *= 2
        self.tree = [0] * (2 * self.n)
 
        for i, value in enumerate(values):
            self.tree[self.n + i] = value
        for i in range(self.n - 1, 0, -1):
            self.tree[i] = self.tree[2 * i] + self.tree[2 * i + 1]

This builds a segment tree for range sums.

Common Confusions

A segment tree is more flexible than a Fenwick tree, but it has more implementation detail.

The combine operation must match the query. Sum, minimum, maximum, and GCD each need the correct identity value and combine rule.

When To Use It

Use a segment tree when there are many range queries and updates, especially when the operation is not as simple as a prefix sum.