15.4 Segment Tree

After the supply line in the algorithm forest was extended, Ah Hua realized that interval inventory checks no longer allowed her to simply start from the beginning and accumulate.

Prelude: Binary Tree and interval boundaries. This page implements point assignment and half-open interval summation; interval batch updates require the lazy propagation contract from the next level.

Total supply volumes are always changing

The inns are arranged in a line along the route. The elder will both ask questions like "How much supply is there from station 3 to station 8?" and occasionally update the inventory at a specific station.

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, let's clearly define the boundaries of the relay zone

"Stations 3 to 8" in plain terms might mean two endpoints or just a vague instruction. If the elders don't first define the boundaries, even the fastest inventory algorithm will steadily calculate incorrectly. Here, we uniformly use a half-open interval.

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

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

When recursively building an empty array, it enters an invalid range and recurses infinitely. This implementation keeps an empty tree with an internal unit leaf capacity, allowing only queries of [0, 0), and point updates fail by contract.

Hide the summary tree in a row of cells

Conceptually, the chain of stations forms an interval tree, and when implementing it, there's no need to create an object for each node. By placing the leaves in the second half of an array and the parent nodes in the first half, you can use indices to find the left and right children and ancestors.

_leaf_count Take the smallest power of 2 that is not less 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, i.e., O(n). This layout is easier to explain than vaguely saying "allocate 4n safely" in terms of what each position means.

Build a reverse in-order merge from the leaves, processing each node once, with time complexity O(n). Successive calls to update for tree construction result in O(n log n), and these two complexities should not be conflated.

A single patrol takes only a summary covering the target

The query team moves inward from both ends of the interval toward the root. When a node is completely within the target, take its stored quantity and stop descending into each station to check individually.

Iteratively query and maintain the unprocessed left and right boundaries. If the left boundary is the right child, the entire segment cannot be merged upward and is immediately added to the result, then the boundary is right-shifted; if the right boundary is one position after the right child, first left-shift, then add the corresponding left segment. Then, both boundaries are moved up to their parent level.

Each layer holds at most two nodes, and the tree height is O(log n), so query time is O(log n). Point updates only require recomputing from the leaf to the root, taking O(log n) time.

Summation satisfies the associative law and has a unit element 0. 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 expression on this page cannot be directly copied.

When a batch of materials changes together, hang a "To-Do" card first

If you add the same inventory to every station in a segment, distributing it station by station loses the advantage of a segment tree. Lazy propagation postpones the update to a covering node and only applies it when a query or further descent occurs; this pending task must specify exactly how to combine the updates, rather than "handle it later alone."

If you add delta to each value inside [left, right), point-wise updates take O(k log n). 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 updates affect aggregated values, such as summing intervals, requires increasing delta * segment_length;
• How do two delayed updates combine;
• 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 a clear algebraic equivalence, there's no reason to paste a "generic lazy template."

Comparison with other interval structures

Requirement	Appropriate Starting Point
Static Range Sum	Prefix Sum
Point update + prefix/interval sum	Fenwick tree or segment tree
Multiple combination aggregation, interval updates	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."

Hands-on Check Interval Boundaries

1. Randomized controlled queries and updates with 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 algorithms forest ends here, and the next volume delves into computer systems.