Sparse Tables and Segment Trees Overview

Many computational problems require repeatedly querying aggregate information across contiguous sub-arrays (e.g., Range Sum Query, Range Minimum Query).

If the array has N elements and you receive Q queries:

• Naive loop per query: O(Q · N) (Too slow for large workloads!).
• Prefix sum array: O(1) sum queries, but cannot answer Range Minimum/GCD queries dynamically when values update.

Enter Sparse Tables and Segment Trees.

1. Sparse Table (Static Range Minimum Query)

A Sparse Table precomputes answers for all sub-arrays whose lengths are powers of two (2ᵏ) using dynamic programming.

Copy codeST[i][j] stores the answer for range [i, i + 2^j - 1]

Key Invariant: Idempotent Operations

For operations where f(x, x) = x (e.g., min, max, gcd): Any range [L, R] can be covered by two overlapping blocks of size 2ᵏ:

min(A[L ... R]) = min(ST[L][k], ST[R - 2ᵏ + 1][k])

• Preprocessing Time: O(N log N)
• Query Time: Strict O(1) Constant Time!
• Limitation: Array must be immutable (static). If elements update, the table must be recomputed.

2. Segment Tree (Dynamic Range Queries with Updates)

A Segment Tree is a binary tree where each node represents an aggregate interval of the array:

• The root represents [0, N-1].
• Children of interval [L, R] are [L, mid] and [mid + 1, R].
• Leaves represent individual elements [i, i].

Copy code                         [0...3] (Sum: 22)
                        /                 \
             [0...1] (Sum: 7)          [2...3] (Sum: 15)
             /              \          /              \
         [0] (3)          [1] (4)    [2] (7)          [3] (8)

Copy codeclass SegmentTree(private val arr: IntArray) {
    private val tree = IntArray(4 * arr.size)

    init { build(0, 0, arr.size - 1) }

    private fun build(node: Int, start: Int, end: Int) {
        if (start == end) {
            tree[node] = arr[start]
        } else {
            val mid = (start + end) / 2
            build(2 * node + 1, start, mid)
            build(2 * node + 2, mid + 1, end)
            tree[node] = tree[2 * node + 1] + tree[2 * node + 2]
        }
    }

    fun query(node: Int, start: Int, end: Int, l: Int, r: Int): Int {
        if (r < start || end < l) return 0 // Out of range
        if (l <= start && end <= r) return tree[node] // Complete overlap
        val mid = (start + end) / 2
        return query(2 * node + 1, start, mid, l, r) + query(2 * node + 2, mid + 1, end, l, r)
    }
}

Comparison Matrix

Summary

• Use Sparse Table for static arrays needing instant O(1) Range Minimum/Maximum queries.
• Use Segment Tree when the underlying array requires frequent updates alongside range queries (O(log N) update and query).