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.

The mechanism is two primitives:

• push(node) — if lazy[node] is nonzero, apply it to the node’s aggregate, defer it onto both children’s lazy slots, then clear node’s lazy. The children’s own values are not touched yet — they’ll absorb the update only when a later query/update actually visits them.
• apply(node, val) — update the aggregate and stack the value into lazy[node].

def push(node, tl, tr):
    if lazy[node] == 0: return
    apply(node*2,   lazy[node])     # defer to left child
    apply(node*2+1, lazy[node])     # defer to right child
    lazy[node] = 0

def range_add(node, tl, tr, ql, qr, v):
    if ql > tr or qr < tl: return                # fully outside
    if ql <= tl and tr <= qr:                    # fully inside
        apply(node, v); return                   # stop — don't descend
    push(node, tl, tr)                           # clear pending before descending
    mid = (tl + tr) // 2
    range_add(node*2,   tl, mid, ql, qr, v)
    range_add(node*2+1, mid+1, tr, ql, qr, v)
    tree[node] = tree[node*2] + tree[node*2+1]

def range_query(node, tl, tr, ql, qr):
    if ql > tr or qr < tl: return 0
    if ql <= tl and tr <= qr: return tree[node]
    push(node, tl, tr)                           # materialize updates first
    mid = (tl + tr) // 2
    return range_query(node*2, tl, mid, ql, qr) \
         + range_query(node*2+1, mid+1, tr, ql, qr)

Every node is visited at most O(log n) times per operation, so both range-add and range-query stay O(log n). The invariant to remember: a node’s aggregate always reflects all updates, but its children may still be waiting — which is why the query pushes before descending. Common extensions build on the same shape: range assignment (set a range to a value) needs a “has-lazy” flag because 0 is a legitimate value, and range max/min with lazy supports the “segment tree beats” family of problems.

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.