Lesson 36.2 · Advanced Data Structures

Segment Trees

A binary tree over the array where each node stores the answer for a segment. Queries combine O(log n) nodes; updates change one leaf and its ancestors.

16 min

Think of it like this

A tournament bracket: each match records the winner of its half. To find the best player in any group, you combine a few match results instead of replaying every game.

1.Iterative segment tree

Store leaves at t[n..2n − 1] and each parent at t[i] = combine(t[2i], t[2i + 1]). A query on [l, r) walks up from both ends, taking a node whenever the range boundary cuts its pair. This compact bottom-up version works for any associative combine (min, max, sum, gcd) and fits in a few lines.

The recursive version (node, node range, query range) is longer but extends to lazy propagation: store pending range updates ("add 5 to everything here") at a node and push them to children only when needed, so range updates also cost O(log n).

Main.java

public class Main {
    static int n;
    static int[] t;

    static void update(int i, int v) {                 // set a[i] = v
        for (t[i += n] = v; i > 1; i >>= 1) t[i >> 1] = Math.min(t[i], t[i ^ 1]);
    }

    static int query(int l, int r) {                   // min of a[l..r)
        int res = Integer.MAX_VALUE;
        for (l += n, r += n; l < r; l >>= 1, r >>= 1) {
            if ((l & 1) == 1) res = Math.min(res, t[l++]);
            if ((r & 1) == 1) res = Math.min(res, t[--r]);
        }
        return res;
    }

    public static void main(String[] args) {
        int[] a = {5, 3, 8, 6, 1, 9, 2, 7};
        n = a.length;
        t = new int[2 * n];
        for (int i = 0; i < n; i++) t[n + i] = a[i];
        for (int i = n - 1; i > 0; i--) t[i] = Math.min(t[2 * i], t[2 * i + 1]);
        System.out.println("min of [0, 4) = " + query(0, 4));
        System.out.println("min of [2, 8) = " + query(2, 8));
        update(4, 10);
        System.out.println("after a[4] = 10, min of [2, 8) = " + query(2, 8));
    }
}

Output

min of [0, 4) = 3
min of [2, 8) = 1
after a[4] = 10, min of [2, 8) = 2

2.Sparse tables for static data

If the array never changes, a sparse table stores the minimum of every block of length 2ᵏ (O(n log n) to build). Because min is idempotent (overlapping blocks don't matter), any range is covered by two blocks: O(1) per query.

Remember

Any associative combine.
O(log n) query and update.
Lazy propagation for range updates; sparse table for static ranges.

Common mistakes

Allocating 2n for the recursive version (it needs up to 4n).
Mixing inclusive and exclusive range ends.

Command Palette

Segment Trees

1.Iterative segment tree

2.Sparse tables for static data