Advanced Trees: Segment Tree, Sparse Table, Interval Tree

Why this module exists

Fenwick trees cover prefix sums, but many problems need range min/max or static queries over immutable arrays. Segment trees and sparse tables are the go-to tools.

Segment tree (dynamic range queries)

A segment tree stores aggregates over intervals. Each node covers a segment, its children cover left/right halves.

• Build: O(n)
• Point update: O(log n)
• Range query: O(log n)

Typical operations: min, max, sum, gcd.

func query(node, l, r, ql, qr int) int {
    if ql <= l && r <= qr { return tree[node] }
    mid := (l + r) / 2
    res := INF
    if ql <= mid { res = min(res, query(node*2, l, mid, ql, qr)) }
    if qr > mid { res = min(res, query(node*2+1, mid+1, r, ql, qr)) }
    return res
}

Lazy propagation extends this to range updates by deferring pushes down.

Sparse table (static range queries)

For idempotent operations (min/max/gcd), you can precompute overlapping blocks of length 2^k.

• Build: O(n log n)
• Query: O(1)

Query uses two blocks: min(l..r) = min(st[k][l], st[k][r-2^k+1])

Interval tree (interval stabbing)

Interval trees store intervals, and each node tracks the max end in its subtree. This lets you quickly find intervals that overlap a point or another interval.

Use cases: scheduling conflicts, range collisions, calendar queries.

What you will build

• Dynamic range minimum queries with a segment tree.
• Static range minimum queries with a sparse table.