Introduction to Segment Tree Pattern

Introduction to Segment Tree Pattern

A Segment Tree works by pre-aggregating an array into a binary tree of overlapping ranges, so that any contiguous query range can be decomposed into at most O(log n) pre-computed segments instead of being rescanned element by element — this is what turns repeated range queries with interleaved updates from O(n) per operation into O(log n) per operation.

Recognize the pattern

• The problem mentions range query (sum/min/max/gcd/xor over [l, r]) interleaved with point or range updates — if updates never happen, a prefix-sum array is simpler and O(1) per query.
• Keywords: "range sum query mutable", "count of smaller after updates", "range minimum with updates", "K-th element by frequency" (Fenwick can also fit, but Segment Tree generalizes to non-invertible ops like min/max/gcd).
• The aggregation operator is associative (sum, min, max, gcd, xor, and) — this is the structural requirement that makes merging children valid.

Brute force to optimal

Brute force: for each query, loop over [l, r] and combine elements directly — O(n) per query, O(1) per update. Fine if queries are rare and updates are frequent.

Precompute prefix sums: O(1) per sum-query, but a single update forces recomputing all prefix sums after it — O(n) per update. Fine only for static arrays.

Segment Tree: O(log n) for both query and update, by storing partial aggregates at every level of a binary decomposition of the array, so a query touches only O(log n) nodes and an update touches only the O(log n) ancestors of one leaf.

Complexity, derived

Build: the tree has height ⌈log₂ n⌉; total nodes across all levels sum to at most 2n − 1 (like a heap), so building bottom-up touches each node once → O(n) time. Space is an array of size 4n in the worst case (a safe upper bound for a non-power-of-2 n stored as a complete binary tree of height ⌈log₂ n⌉ + 1; index i's children sit at 2i, 2i+1).

Query(l, r): at each recursion level the current segment either lies fully inside, fully outside, or straddles [l, r]. A straddling segment recurses into exactly 2 children, but crucially at most 4 nodes per level ever straddle (bounded by the two boundary paths from root to l and root to r) — so total nodes visited is O(log n) per level × log n levels → O(log n) time, O(log n) recursion-stack space.

Update(i, val): only the single root-to-leaf path containing index i needs recomputation — that path has exactly ⌈log₂ n⌉ + 1 nodes → O(log n) time and space.

Worked example — range sum, array [2, 4, 6, 8, 10, 12]

Query sum(1, 3) — asking for indices 1..3 (values 4, 6, 8 → expected 18). Tracing the Java query() against this tree node by node:

1. node1 [0,5]: straddles → recurse into node2 and node3.
2. node2 [0,2]: straddles (query covers indices 1,2 of its 0,1,2) → recurse into node4 [0,1] and node5 [2,2].
3. node4 [0,1]: straddles (query starts at 1, inside [0,1]) → recurse into node8 (leaf idx0) and node9 (leaf idx1).
4. node8, leaf idx0: fully outside (hi=0 < l=1) → pruned, contributes 0.
5. node9, leaf idx1: fully inside (l=1 ≤ lo=1, hi=1 ≤ r=3) → contributes 4.
6. node5 [2,2]: fully inside (1 ≤ 2, 2 ≤ 3) → take 6 directly, no further recursion.
7. node3 [3,5]: straddles (query covers only index 3 of its 3,4,5) → recurse into node6 [3,4] and node7 [5,5].
8. node6 [3,4]: straddles → recurse into node12 (leaf idx3) and node13 (leaf idx4).
9. node12, leaf idx3: fully inside → contributes 8.
10. node13, leaf idx4: fully outside (r=3 < lo=4) → pruned, contributes 0.
11. node7 [5,5]: fully outside (r=3 < lo=5) → pruned, contributes 0.

Sum returned: 4 + 6 + 8 = 18. ✓ Nodes visited (recursive calls made): 11 — node1, node2, node3, node4, node5, node6, node7, node8, node9, node12, node13 — comfortably within the O(log n)-per-level bound for n=6 (⌈log₂6⌉=3 levels below root, at most 4 straddling nodes per level).

Update index 2 from 6 to 7: walk the path node1 → node2 → node5 (the leaf holding index 2), set the leaf to 7. Recompute ancestors bottom-up: node2 = [0,1] + [2,2] = node4 + node5 = 6 + 7 = 13 (node4=[0,1] is unaffected since index 2 isn't in range [0,1], so it stays 6). Then root = node2 + node3 = 13 + 30 = 43.

Java implementation (iterative-build, sum range tree)

class SegmentTree {
    private final int[] tree;
    private final int n;

    SegmentTree(int[] arr) {
        n = arr.length;
        tree = new int[4 * n];
        build(arr, 1, 0, n - 1);
    }

    private void build(int[] arr, int node, int lo, int hi) {
        if (lo == hi) { tree[node] = arr[lo]; return; }
        int mid = (lo + hi) / 2;
        build(arr, 2 * node, lo, mid);
        build(arr, 2 * node + 1, mid + 1, hi);
        tree[node] = tree[2 * node] + tree[2 * node + 1];
    }

    // sum over [l, r]
    int query(int node, int lo, int hi, int l, int r) {
        if (r < lo || hi < l) return 0;              // fully outside
        if (l <= lo && hi <= r) return tree[node];    // fully inside
        int mid = (lo + hi) / 2;
        return query(2 * node, lo, mid, l, r)
             + query(2 * node + 1, mid + 1, hi, l, r);
    }

    void update(int node, int lo, int hi, int idx, int val) {
        if (lo == hi) { tree[node] = val; return; }
        int mid = (lo + hi) / 2;
        if (idx <= mid) update(2 * node, lo, mid, idx, val);
        else update(2 * node + 1, mid + 1, hi, idx, val);
        tree[node] = tree[2 * node] + tree[2 * node + 1];
    }
}

Pitfalls

• Undersizing the array: using 2n instead of 4n causes ArrayIndexOutOfBounds for non-power-of-2 n — the recursion tree can be unbalanced enough to need up to 4n slots.
• Off-by-one in split: mixing up mid vs mid+1 boundaries silently drops or double-counts an element.
• Using sum-merge logic for non-invertible ops: range-update-with-lazy-propagation is easy to get wrong for min/max (no simple "subtract" undo) — must design the lazy tag per operator.
• Forgetting lazy propagation when doing range updates (e.g. "add v to every element in [l,r]") — without it, range update degrades back to O(n).

When to use / when not — trade-offs vs Fenwick Tree (BIT)

Use a Segment Tree when the aggregate is non-invertible (min/max/gcd) or you need range updates on arbitrary ops. Prefer a Fenwick Tree when the op is just sum/xor and you want minimal code and better constants. Use neither (plain prefix sums) if the array is static — no updates ever.

Takeaways

• Segment Tree pre-aggregates overlapping ranges in a binary tree so any query decomposes into O(log n) precomputed pieces.
• Build is O(n), query and point-update are both O(log n) time, O(log n) space (recursion stack); array storage needs size 4n.
• Requires an associative merge operator; add lazy propagation only when range (not point) updates are needed.
• Prefer Fenwick Tree for simple invertible sum/xor cases — reach for Segment Tree when you need min/max/gcd or range updates.

Recall: Why must the merge operator be associative, and what breaks if you use a Segment Tree for a non-associative operator like average?

Compiled from standard competitive-programming and interview-prep references on Segment Trees (array-based binary indexed range structures); complexity derivations and Java implementation verified by hand-tracing against the worked example.