SyntaxPilot
Courses/DSA and Coding Problems/Lesson 84
Video coming soonThis lesson’s video is being made

Start with the notes below; the video appears here as soon as it is on YouTube.

DSA and Coding Problems · Lesson 84 of 90

Sparse table and range minimum query

queued

These are the notes for DSA episode 84. A weather station has one temperature per day for thirty years, and a weather app asks "what was the coldest reading between day l and day r?" a million times. The past never changes. We try the obvious way, scanning the range (correct, then Time Limit Exceeded on a million days and a million questions). A segment tree (episode 82) would give O(log n), but because the data is static we can precompute more: the minimum of every block whose length is a power of two, each level built from two halves of the level below. Any range is then covered by two blocks of the same length that may overlap, and overlap is harmless for a minimum: O(1) per query. Then three real bugs: the same trick for a sum, a build loop that stops one block early, and a second block that misses the last element. Every program below was run with javac 21 (25-second limit, like the SyntaxPilot compiler), g++ 13 and Python 3, and every output shown is real (timings vary by machine).

The problem, in real life

The weather station In code
One reading per day for 30 years the array a, length n
"Coldest day from l to r?" minRange(l, r)
The past never changes static array: build once, no updates
Coldest of each week, fortnight, month (pre-written) the levels of the sparse table

Every word, from zero

  • Range minimum query (RMQ): the smallest value in a[l..r].
  • Static data: data that never changes after it is built (no updates).
  • Precompute: do work once, in advance, so that every later question is cheap.
  • Power of two: 1, 2, 4, 8, 16, …: 2ᵏ, written 1 << k in Java (shift 1 left by k bits).
  • Level k: all blocks of length 2ᵏ.
  • Sparse table: st[k][i] = the minimum of the block of length 2ᵏ starting at i.
  • Floor of log₂: lg[x] = the largest k with 2ᵏ ≤ x (lg[6] = 2).
  • Idempotent operation: doing it twice with the same element changes nothing: min(x, x) = x, also max and gcd. Sum is not idempotent.
  • Overlap: two ranges share some indices.
  • Binary lifting: building jumps of length 2ᵏ from two jumps of length 2ᵏ⁻¹; the same doubling idea.
  • Checksum: one number combining many answers, used to compare programs quickly.

Problem statement

Build a structure from an array a that never changes, then answer minRange(l, r) = min(a[l..r]) (both ends included). n and the number of queries can each be a million.

Query on a = 5 8 3 9 6 2 7 4 Answer Why
minRange(1, 6) 2 min of 8 3 9 6 2 7
minRange(0, 4) 3 min of 5 8 3 9 6
minRange(0, 7) 2 the whole array
minRange(3, 3) 9 one element
minRange(6, 7) 4 the last two
[-12], minRange(0, 0) -12 an array of one negative number

Obvious idea: scan the range

import java.util.*;

public class Main {
    static int[] arr;
    static void build(int[] a) { arr = a.clone(); }
    static int minRange(int l, int r) {
        int m = arr[l];
        for (int k = l + 1; k <= r; k++) m = Math.min(m, arr[k]);
        return m;
    }
    public static void main(String[] args) {
        build(new int[]{5, 8, 3, 9, 6, 2, 7, 4});
        System.out.println(minRange(1, 6) + " " + minRange(0, 4) + " " + minRange(0, 7));
        System.out.println(minRange(3, 3) + " " + minRange(6, 7));
        build(new int[]{-12});
        System.out.println(minRange(0, 0));
    }
}

Output (real):

2 3 2
9 4
-12

The big test

A million readings in −50..50 and a million random queries from new Random(3); we print a checksum of the answers and the time:

        int n = 1_000_000;
        int[] a = new int[n];
        Random rnd = new Random(3);
        for (int i = 0; i < n; i++) a[i] = rnd.nextInt(101) - 50;
        long t0 = System.nanoTime(), check = 0;
        build(a);
        for (int q = 0; q < 1_000_000; q++) {
            int i = rnd.nextInt(n), j = rnd.nextInt(n);
            check += minRange(Math.min(i, j), Math.max(i, j));
        }
        System.out.println(check + ", " + (System.nanoTime() - t0) / 1000000 + " ms");

Result with the scan: Time Limit Exceeded (25 s). Each query reads a third of a million numbers on average: about 3 × 10¹¹ steps.

The key insight: minimums of power-of-two blocks

Storing every range would be n(n + 1)/2 answers. Store only blocks whose length is a power of two: about n log₂ n numbers (20 million for a million days).

st[0][i] = a[i]
st[k][i] = min(st[k-1][i], st[k-1][i + 2^(k-1)])     a 2^k block = two 2^(k-1) blocks side by side

For a = 5 8 3 9 6 2 7 4:

Level Block length Values (starting at i = 0, 1, 2, …)
0 1 5 8 3 9 6 2 7 4
1 2 5 3 3 6 2 2 4
2 4 3 3 2 2 2
3 8 2

The query: two blocks, one comparison

len = r - l + 1,   k = lg[len]     (largest k with 2^k <= len)
answer = min(st[k][l], st[k][r - 2^k + 1])

The first block starts at l, the second ends at r, and each is longer than half the range, so together they cover l..r. For minRange(1, 6): len = 6, k = 2, blocks [1..4] (3) and [3..6] (2): 2. They overlap on 3..4, which is fine for min (counting a value twice does not change the smallest), but would be wrong for a sum.

lg is precomputed with integers: lg[1] = 0, lg[i] = lg[i / 2] + 1. (Java alternative: 31 - Integer.numberOfLeadingZeros(len).)

Solution in Java: the sparse table

import java.util.*;

public class Main {
    static int[][] st;
    static int[] lg;
    static void build(int[] a) {
        int n = a.length;
        lg = new int[n + 1];
        for (int i = 2; i <= n; i++) lg[i] = lg[i / 2] + 1;
        st = new int[lg[n] + 1][];
        st[0] = a.clone();
        for (int k = 1; k <= lg[n]; k++) {
            st[k] = new int[n - (1 << k) + 1];
            for (int i = 0; i + (1 << k) <= n; i++)
                st[k][i] = Math.min(st[k - 1][i], st[k - 1][i + (1 << (k - 1))]);
        }
    }
    static int minRange(int l, int r) {
        int k = lg[r - l + 1];
        return Math.min(st[k][l], st[k][r - (1 << k) + 1]);
    }
    public static void main(String[] args) {
        build(new int[]{5, 8, 3, 9, 6, 2, 7, 4});
        System.out.println(minRange(1, 6) + " " + minRange(0, 4) + " " + minRange(0, 7));
        System.out.println(minRange(3, 3) + " " + minRange(6, 7));
        build(new int[]{-12});
        System.out.println(minRange(0, 0));
    }
}

Output (real):

2 3 2
9 4
-12

On the big test: -49999105, 247 ms (build included), where the scan timed out.

The same solution in C++

#include <bits/stdc++.h>
using namespace std;

vector<vector<int>> st;
vector<int> lg;

void build(const vector<int>& a) {
    int n = a.size();
    lg.assign(n + 1, 0);
    for (int i = 2; i <= n; i++) lg[i] = lg[i / 2] + 1;
    st.assign(lg[n] + 1, {});
    st[0] = a;
    for (int k = 1; k <= lg[n]; k++) {
        st[k].resize(n - (1 << k) + 1);
        for (int i = 0; i + (1 << k) <= n; i++)
            st[k][i] = min(st[k - 1][i], st[k - 1][i + (1 << (k - 1))]);
    }
}

int minRange(int l, int r) {
    int k = lg[r - l + 1];
    return min(st[k][l], st[k][r - (1 << k) + 1]);
}

int main() {
    build({5, 8, 3, 9, 6, 2, 7, 4});
    cout << minRange(1, 6) << " " << minRange(0, 4) << " " << minRange(0, 7) << "\n";
    cout << minRange(3, 3) << " " << minRange(6, 7) << "\n";
    build({-12});
    cout << minRange(0, 0) << "\n";
}

Output (real):

2 3 2
9 4
-12

The same solution in Python

def build(a):
    n = len(a)
    lg = [0] * (n + 1)
    for i in range(2, n + 1):
        lg[i] = lg[i // 2] + 1
    st = [a[:]]
    for k in range(1, lg[n] + 1):
        prev, half = st[k - 1], 1 << (k - 1)
        st.append([min(prev[i], prev[i + half]) for i in range(n - (1 << k) + 1)])
    return st, lg


def min_range(table, l, r):
    st, lg = table
    k = lg[r - l + 1]
    return min(st[k][l], st[k][r - (1 << k) + 1])


t = build([5, 8, 3, 9, 6, 2, 7, 4])
print(min_range(t, 1, 6), min_range(t, 0, 4), min_range(t, 0, 7))
print(min_range(t, 3, 3), min_range(t, 6, 7))
print(min_range(build([-12]), 0, 0))

Output (real):

2 3 2
9 4
-12

Three real bugs

Bug 1: the same trick for a range sum

Swap Math.min for +, and ask for sum(1..6) (8 + 3 + 9 + 6 + 2 + 7 = 35):

50

The blocks [1..4] and [3..6] share 9 and 6, which were added twice. For sums use prefix sums, a Fenwick tree or a segment tree.

Bug 2: the build loop stops one block early

With i + (1 << k) < n the last block of each level is never filled and keeps Java's default 0. minRange(0, 7):

0

There is no 0 in the array. A block may end exactly at index n − 1: use <=.

Bug 3: the second block starts at r − 2ᵏ

Without + 1 the second block slides one place left and misses a[r]. minRange(3, 5) (9 6 2):

6

Expected 2.

Complexity

Approach Build Query Space Updates Big test (10⁶ days, 10⁶ queries)
Scan the range O(n) O(n) O(n) O(1) Time Limit Exceeded
Segment tree (min) O(n) O(log n) O(n) O(log n) fast
Sparse table O(n log n) O(1) O(n log n) rebuild: O(n log n) 247 ms

Choose the sparse table when the array never changes and there are very many queries; a segment tree when it changes.

Common mistakes

Mistake What you see (real) Why Fix
Same trick for sum 50 instead of 35 the overlap is added twice only min, max, gcd (idempotent)
i + (1 << k) < n in the build 0, not in the array the last block was never filled i + (1 << k) <= n
st[k][r - (1 << k)] 6 instead of 2 block 2 misses a[r] r - (1 << k) + 1
k from Math.log(len) / Math.log(2) slower, and a rounding risk floating point (Math.log(243) / Math.log(3) is 4.999999999999999, not 5) integer lg[] table
Too few levels, e.g. a fixed LOG = 16 for n = 10⁶ ArrayIndexOutOfBoundsException lg[n] is 19 size the table by lg[n] + 1
1 << k written as 2 ^ k wrong blocks ^ is XOR in Java, not a power 1 << k

Mini project: weather app back end

Load a CSV of daily temperatures. Build two sparse tables (min and max) and answer commands like coldest 2001-01-01 2001-12-31 and hottest …, converting dates to day indices. Compare the time for 100,000 queries with a scan.

Practice

1. Range maximum. Change min to max.

2. Range GCD of 12 18 24 9 27.

3. Sliding Window Maximum (LeetCode 239) with a max sparse table (an O(n log n) alternative to the monotonic deque).

4. Build the table for 4 1 3 2 by hand.

Solutions
import java.util.*;
import java.util.function.IntBinaryOperator;

public class Main {
    // One sparse table for any idempotent operation: min, max, gcd.
    static class Sparse {
        int[][] st; int[] lg; IntBinaryOperator op;
        Sparse(int[] a, IntBinaryOperator op) {
            this.op = op;
            int n = a.length;
            lg = new int[n + 1];
            for (int i = 2; i <= n; i++) lg[i] = lg[i / 2] + 1;
            st = new int[lg[n] + 1][];
            st[0] = a.clone();
            for (int k = 1; k <= lg[n]; k++) {
                st[k] = new int[n - (1 << k) + 1];
                for (int i = 0; i + (1 << k) <= n; i++)
                    st[k][i] = op.applyAsInt(st[k - 1][i], st[k - 1][i + (1 << (k - 1))]);
            }
        }
        int query(int l, int r) {
            int k = lg[r - l + 1];
            return op.applyAsInt(st[k][l], st[k][r - (1 << k) + 1]);
        }
    }
    static int gcd(int a, int b) { return b == 0 ? a : gcd(b, a % b); }
    // 3. Sliding Window Maximum (LeetCode 239) with a max sparse table: O(n log n).
    static int[] maxSlidingWindow(int[] nums, int k) {
        Sparse mx = new Sparse(nums, Math::max);
        int[] res = new int[nums.length - k + 1];
        for (int i = 0; i + k <= nums.length; i++) res[i] = mx.query(i, i + k - 1);
        return res;
    }
    public static void main(String[] args) {
        int[] a = {5, 8, 3, 9, 6, 2, 7, 4};
        Sparse mx = new Sparse(a, Math::max);                 // 1. range maximum
        System.out.println(mx.query(1, 6) + " " + mx.query(4, 7));
        Sparse g = new Sparse(new int[]{12, 18, 24, 9, 27}, Main::gcd);   // 2. range GCD
        System.out.println(g.query(0, 2) + " " + g.query(2, 4) + " " + g.query(0, 4));
        System.out.println(Arrays.toString(maxSlidingWindow(new int[]{1, 3, -1, -3, 5, 3, 6, 7}, 3)));
        Sparse mn = new Sparse(new int[]{4, 1, 3, 2}, Math::min);        // 4. the table for 4 1 3 2
        for (int[] row : mn.st) System.out.println(Arrays.toString(row));
    }
}

Output (real):

9 7
6 3 3
[3, 3, 5, 5, 6, 7]
[4, 1, 3, 2]
[1, 1, 2]
[1]

Quick quiz

For minRange(2, 7), which two blocks are compared? A) st[2][2] and st[2][4] B) st[2][2] and st[2][3] C) st[1][2] and st[1][6] D) st[3][0] only

Answer

A. The length is 6, lg[6] = 2 (blocks of 4): one starts at l = 2, the other at r − 4 + 1 = 4. They cover 2..5 and 4..7.

Interview questions

  1. Sparse table or segment tree? Sparse table: static data, O(1) min/max queries. Segment tree: updates, or operations like sum.
  2. Why may the two blocks overlap? Because min is idempotent: counting an element twice changes nothing.
  3. Why is the build O(n log n)? About log n levels, each with up to n blocks, each computed in O(1) from the level below.
  4. How do you find k quickly? A precomputed lg[] table or 31 - Integer.numberOfLeadingZeros(len).
  5. Can a sparse table answer range sums? Yes, in O(log n), by splitting the range into disjoint power-of-two blocks, but prefix sums are simpler.
  6. Where else is the doubling idea used? Binary lifting for the k-th ancestor and LCA in trees.

Glossary

Term Meaning
Range minimum query (RMQ) The smallest value in a[l..r]
Static data Never changes after it is built
Precompute Work done once in advance
Power of two 2ᵏ, written 1 << k
Level k All blocks of length 2ᵏ
Sparse table st[k][i] = min of the 2ᵏ block at i
lg[x] The largest k with 2ᵏ ≤ x
Idempotent Applying it twice changes nothing (min, max, gcd)
Overlap Two ranges share indices
Binary lifting Building 2ᵏ jumps from two 2ᵏ⁻¹ jumps

Summary

  • Scanning is O(n) per query: a million questions time out.
  • Static data lets us precompute the minimum of every power-of-two block, each level from two halves of the level below: O(n log n).
  • A query compares two blocks of length 2^lg[len], one starting at l, one ending at r: O(1).
  • The overlap trick works for min, max and gcd, never for sum.
  • Fill the last block (<=), end the second block at r (+ 1), and use an integer log table.
  • Next episode: matrix problems: rotate image, spiral order, set matrix zeroes.