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).

Class Contract

SegmentTree(values) builds a range-sum tree over the input values.

update(index, value) replaces one array position with a new value. range_sum(left, right) returns the sum over inclusive indexes from left through right.

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]
 
    def update(self, index, value):
        position = self.n + index
        self.tree[position] = value
 
        position //= 2
        while position >= 1:
            self.tree[position] = (
                self.tree[2 * position] + self.tree[2 * position + 1]
            )
            position //= 2
 
    def range_sum(self, left, right):
        left += self.n
        right += self.n
        total = 0
 
        while left <= right:
            if left % 2 == 1:
                total += self.tree[left]
                left += 1
            if right % 2 == 0:
                total += self.tree[right]
                right -= 1
            left //= 2
            right //= 2
 
        return total

This segment tree supports point updates and inclusive range-sum queries.

Query Shape

A range query splits the requested interval into a small number of stored segments. For example, a query over [left, right] may combine a few complete tree nodes instead of scanning every element.

The combine operation must be associative, such as:

(a + b) + c = a + (b + c)

Sum, minimum, maximum, and GCD all work with the right identity value.

In the iterative range_sum code, left and right first move to leaf positions. When left is a right child, its segment is fully inside the query and can be used before moving to the next segment. When right is a left child, its segment is fully inside the query and can be used before moving left.

Point Update

For a point update, change one leaf and recompute ancestors up to the root. Only O(log n) tree nodes are affected because the tree height is logarithmic.

In the code, update changes one leaf and then repeatedly recomputes the parent from its two children.

Step-by-Step Example

For values = [2, 1, 5, 3], the root stores the sum 11. Its children store sums for [2, 1] and [5, 3], which are 3 and 8.

A query for indexes 1..2 should return 1 + 5 = 6. The segment tree answers by combining stored pieces that exactly cover that range, rather than scanning every index.

Complexity

Building the tree is O(n). Range query and point update are O(log n) for common implementations. The tree uses O(n) space, often with a constant factor such as 2n or 4n.

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.

Another common mistake is using a segment tree when a prefix sum would solve a static range-sum problem more simply.

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.

Use lazy propagation when the updates affect whole ranges rather than single points.

The Main Point

A segment tree decomposes ranges into stored segments. It is useful when both queries and updates must stay logarithmic.