Segment Tree

A Segment Tree is a binary tree over an array, where each node stores an aggregate (sum, min, max, gcd) for the array segment it covers. It answers range queries and point updates in O(log n), with O(n) construction.

The Structure

• Each leaf covers exactly one array element.
• Each internal node covers the union of its children’s segments.
• The root covers the whole array [0, n-1].

            [0,5]=26
           /        \
     [0,2]=8        [3,5]=18
     /     \        /     \
 [0,1]=7  [2,2]=1 [3,4]=11 [5,5]=7
 /    \
[0]=2 [1]=5

Stored in a flat array of size ~4n: node i has children 2i and 2i+1.

Range Query in O(log n)

A query [ql, qr] walks the tree with a simple rule:

• Fully inside [ql, qr] → return the node’s aggregate, stop.
• Fully outside → return the identity (0 for sum), stop.
• Partial overlap → recurse into both children.

At most O(log n) nodes are visited in full, because the query is broken into O(log n) canonical segments.

Point Update in O(log n)

Update index idx: descend from the root to the leaf idx, change the value, then recompute the aggregate on the way back up. Only O(log n) nodes on the root-to-leaf path change.

Lazy Propagation

To support range updates (e.g. “add 5 to all of [l, r]”) without touching every element, store pending updates at internal nodes and only push them down when a query actually descends into those nodes. This keeps range updates at O(log n) too, at the cost of an extra lazy array.

When It’s the Right Tool

Practice Trajectory

1. Build a sum segment tree and verify queries by hand.
2. Implement query and update recursively — this is the whole algorithm.
3. Switch the aggregate to min/max/gcd — note nothing else changes.
4. Implement lazy propagation and a range-add update.
5. Solve: range-sum-with-updates, K-th smallest in a subarray, segment-tree-beats style problems.