15.4 Segment Tree

Prerequisites: Binary Tree and interval boundaries. This page implements point assignment and half-open interval summation; interval batch updates require additional rules for lazy propagation.

Range Totals and Point Values Both Change

Prefix sums can answer static range sum queries in O(1) time, but a point update affects many subsequent prefixes. Direct array updates are cheap, but range queries require scanning. A segment tree strikes a balance between the two: leaf nodes store individual point values, and parent nodes store the sum of their child intervals.

A single point update modifies only one path from a leaf to the root; a range query breaks the target into O(log n) disjoint tree-node intervals.

First Define the Query Interval

"Index 3 through index 8" may include both endpoints or use an exclusive right endpoint. If the API does not define that boundary first, even a fast implementation will return consistently wrong results. This lesson uses half-open intervals.

The implementation copies an iterable of integers; update values must also be integers, excluding booleans. Invalid values raise TypeError during construction or update. Invalid indices and ranges raise IndexError. Length is fixed, and both index and value are checked before updating.

This page uses [left, right): contains left, does not contain right. The sum of the empty interval [i, i) is 0; the entire array is [0, n). This convention aligns with Python slicing, and ensures that adjacent intervals [a, b) and [b, c) do not overlap or have gaps.

class SumSegmentTree:
    def __init__(self, values):
        data = list(values)
        for value in data:
            self._check_value(value)
        self.length = len(data)
        self._leaf_count = 1
        while self._leaf_count < self.length:
            self._leaf_count *= 2

        self._tree = [0] * (2 * self._leaf_count)
        for index, value in enumerate(data):
            self._tree[self._leaf_count + index] = value
        for node in range(self._leaf_count - 1, 0, -1):
            self._tree[node] = self._tree[2 * node] + self._tree[2 * node + 1]

    @staticmethod
    def _check_value(value):
        if not isinstance(value, int) or isinstance(value, bool):
            raise TypeError("values must be integers")

    def _check_index(self, index):
        if (
            not isinstance(index, int)
            or isinstance(index, bool)
            or not 0 <= index < self.length
        ):
            raise IndexError(f"index out of range: {index!r}")

    def update(self, index, value):
        self._check_index(index)
        self._check_value(value)
        node = self._leaf_count + index
        self._tree[node] = value
        node //= 2
        while node:
            self._tree[node] = self._tree[2 * node] + self._tree[2 * node + 1]
            node //= 2

    def query(self, left, right):
        if (
            not isinstance(left, int)
            or isinstance(left, bool)
            or not isinstance(right, int)
            or isinstance(right, bool)
            or not 0 <= left <= right <= self.length
        ):
            raise IndexError(f"invalid half-open range: [{left!r}, {right!r})")

        left += self._leaf_count
        right += self._leaf_count
        total = 0
        while left < right:
            if left & 1:
                total += self._tree[left]
                left += 1
            if right & 1:
                right -= 1
                total += self._tree[right]
            left //= 2
            right //= 2
        return total

if __name__ == "__main__":
    tree = SumSegmentTree([1, 3, 5, 7, 9, 11])
    assert tree.query(1, 4) == 15
    tree.update(2, 6)
    assert tree.query(1, 4) == 16
    assert tree.query(0, tree.length) == 37
    assert tree.query(3, 3) == 0

    empty = SumSegmentTree([])
    assert empty.query(0, 0) == 0
    print("Segment tree passes check")

An empty tree retains one internal leaf position, avoiding recursive handling of an empty interval. Only [0, 0) may be queried; point updates raise IndexError. Unlike Python slicing, out-of-range endpoints are not clipped and reversed ranges are not treated as empty.

Store the Tree in an Array

_leaf_count is the smallest power of two no smaller than n. Leaves start from this index, and unused leaf positions remain as the additive identity 0. For any internal node p:

tree[p] = tree[2*p] + tree[2*p+1]

The root is at index 1, index 0 is left empty. The total array length is 2 * leaf_count, or Θ(n+1), including the two slots for empty input. This layout is easier to explain than vaguely saying "allocate 4n safely" in terms of what each position means.

Build by visiting internal array indices in descending order, processing each node once in Θ(n+1) time. Building through n successive calls to update instead takes O(n log(n+1)).

A Query Merges Only the Summaries That Cover Its Target

Maintain the unprocessed half-open range. An odd left index is a right child whose left sibling lies outside the target: take that node and increment the left boundary. An odd right index is an excluded right child: decrement the right boundary and take its left sibling. The remaining boundaries align with sibling pairs, so divide both by 2 to move up.

With leaf capacity 8, querying [1,6) starts at (9,14) and takes node 9. Moving up yields (5,7), where nodes 5 and 6 are taken. The three nodes cover [1,2), [2,4), and [4,6) without overlap or omission.

Each level contributes at most two nodes, and tree height is O(log(n+1)). Queries and point updates on nonempty trees take O(log(n+1)) time and O(1) extra iterative workspace; a valid empty-tree query takes O(1). These bounds count integer addition as constant time; big integers also incur bit-length costs.

Integer addition is associative and has identity 0. Floating-point addition is not strictly associative, which is why this implementation restricts values to integers. A segment tree can maintain minimum, maximum, GCD, or a custom associative operation; if the operation does not satisfy the associative law, combining segments in different orders may alter the result. If the operation does not satisfy the commutative law, the merging order of left and right segments must be preserved, and the single total accumulator cannot be reused unchanged. Keep left and right results separately: append on the left with combine(left_total, node), prepend on the right with combine(node, right_total), then combine the two results. AtCoder Library’s segment-tree interface explicitly states associativity, identity, and operation-cost requirements.

Record a Deferred Update When an Entire Range Changes

If you add delta to each value inside [left, right), point-wise updates take O(k log(n+1)), where k=right-left. Lazy propagation temporarily stores "updates that apply to entire segments" in cover nodes and pushes them down to children only when querying or descending further, thereby reducing interval updates to O(log n).

This requires additional definition:

• How an update affects an aggregate: a range sum increases by delta * segment_length;
• How two pending updates compose;
• When to push the marker down and clear it.

The marking rules for interval addition, interval assignment, and affine transformations are different. Without first establishing the algebraic contract, there's no reason to paste a "generic lazy template."

Compare Range Structures

Requirement	Appropriate Starting Point
Static Range Sum	Prefix Sum
Point update + prefix/interval sum	Fenwick tree or segment tree
Associative aggregates; range updates that act on summaries and compose efficiently	Segment tree
Static RMQ	sparse table, etc. static structures

Fenwick trees typically have shorter code and smaller constants, but their supported algebraic operations and query forms are more restricted. The actual choice should be based on the operation set, memory constraints, and implementation complexity, not on a hierarchy of "advancedness."

Check the Interval Boundaries

1. Compare random queries and updates against Python sum(values[left:right]).
2. Change the aggregation to minimum; what should be returned for an empty interval as the unit element?
3. Implement a function that returns the sum of a range while supporting point-wise increments, rather than point-wise assignments.
4. Prove _leaf_count < 2n (n > 0), thus showing O(n) storage.
5. Design a lazy tag for interval addition, and write the update formulas for parent and child nodes.

Last Ancestral Chain

A segment tree doesn't store the answer to each query; it only keeps reusable interval summaries. After a point update, only one ancestral chain becomes invalid; queries reconstruct the desired interval from these summaries.

Go back to Chapter 15 Overview to compare Bloom filters, union-find, segment trees, and the Trie discussed earlier. The next volume moves into Computer Systems.