Static Range Minimum Query

Problem in Plain English

Preprocess a fixed array to answer inclusive range minimum queries with a Sparse Table. Combine two overlapping power-of-two blocks in constant time.

Problem Statement

This page solves CSES Static Range Minimum Queries. Read n q, then n integers, then q pairs a b. For each pair print the minimum element from position a through b inclusive. Input endpoints are one-based; the array never changes. The public task has no difficulty rating. The complete programs below convert each endpoint to zero-based and print one result per line.

Constraints

1 <= n,q <= 2 × 10^5.
1 <= x[i] <= 10^9.
1 <= a <= b <= n; endpoints are inclusive and one-based.
The input array is static; updates are outside this exercise.

Examples

Example 1

Input: 8 4 3 2 4 5 1 1 5 3 2 4 5 6 1 8 3 3
Output: 2 1 1 4

The four inclusive intervals have minima 2,1,1,4. The last query contains only the third value.

Example 2

Input: 1 1 1000000000 1 1
Output: 1000000000

A singleton uses two identical length-one blocks, whose minimum remains that value.

Example 3

Input: 5 3 9 8 7 6 5 1 5 2 4 4 5
Output: 5 6 5

Lengths five and three use overlapping blocks; the final length-two query uses one stored interval at both ends.

Intuition

Store minima for intervals of lengths 1,2,4,8 and so on. A query need not decompose into many disjoint blocks: choose the largest power of two no longer than the query and cover it with one block at each end. The two blocks overlap, but min(x,x)=x, so repeated elements do not change the result. In Example 1 the query [2,4] has length 3; blocks [2,3] and [3,4] both contain position 3 and their minima are 2 and 4. The answer is 2.

Approaches

Sparse Table

Optimal

Solution Details

Reveal Sparse Table: intuition, complexity, and code

Intuition

Precompute table[k][i], the minimum of the length-2^k block starting at i. Level zero copies the values. A larger block combines two adjacent blocks from the preceding level: min(table[k-1][i], table[k-1][i+2^(k-1)]). For a zero-based inclusive query [l,r], let k=floor(log2(r-l+1)) and width=2^k. Return min(table[k][l], table[k][r-width+1]). Precomputed integer logs avoid floating-point boundary errors. Scanning every query costs O(n) each; this spends O(n log n) preprocessing to make each query O(1).

Step-by-Step Logic

Level zero is [3,2,4,5,1,1,5,3]; length-two minima are [2,2,4,1,1,1,3].
Length-four minima are [2,1,1,1,1]; length-eight minimum is [1].
Query [2,4] converts to [1,3], length 3, k=1: use starts 1 and 2, minima 2 and 4, answer 2.
Query [5,6] converts to [4,5], k=1: both block starts are 4, answer 1.
Query [1,8] uses the length-eight block at start 0, answer 1.
Query [3,3] uses level zero at start 2, answer 4; print 2,1,1,4 on separate lines.

Why It Works

Induction on k proves each table cell: level zero is a single input value and the two halves exactly partition a larger block. For a query of length m, the chosen width satisfies width <= m < 2×width, so the block anchored at the left and the block anchored at the right stay inside the query and together cover it. Their overlap repeats only elements already in the range. Minimum is associative and idempotent, so combining both minima is the minimum over the entire query. This would fail for sums because overlapping values would be counted twice.

Dry Run

Sparse Table: variable states at each step
Query	Zero-based endpoints	k / width	Block starts	Block minima	Output so far
[2,4]	[1,3]	1 / 2	1,2	2,4	[2]
[5,6]	[4,5]	1 / 2	4,4	1,1	[2,1]
[1,8]	[0,7]	3 / 8	0,0	1,1	[2,1,1]
[3,3]	[2,2]	0 / 1	2,2	4,4	[2,1,1,4] (one per line)

Complexity Analysis

Time Complexity

O(n log n + q)

Space Complexity

O(n log n + q)

The table contains logarithmically many levels of up to n entries, integer logs are linear, and q queries take constant time each. Buffered input/output in these complete programs adds O(n+q) storage, including the q output lines. Values are compared rather than summed, so Java int and JavaScript Number are exact under the source bounds. A point change can affect linearly many stored blocks; rebuilding is O(n log n), unlike a Segment Tree update.

Code

Solution.java

1import java.io.*;2public class Main {3    static class SparseTable {4        final int[] log;5        final int[][] table;6        SparseTable(int[] values) {7            int n = values.length;8            log = new int[n + 1];9            for (int i = 2; i <= n; i++) log[i] = log[i / 2] + 1;10            table = new int[log[n] + 1][];11            table[0] = values.clone();12            for (int k = 1; k < table.length; k++) {13                int width = 1 << k, half = width / 2;14                table[k] = new int[n - width + 1];15                for (int i = 0; i < table[k].length; i++)16                    table[k][i] = Math.min(table[k - 1][i], table[k - 1][i + half]);17            }18        }19        int query(int l, int r) {20            int k = log[r - l + 1], width = 1 << k;21            return Math.min(table[k][l], table[k][r - width + 1]);22        }23    }24    static class FastInput {25        final InputStream in = new BufferedInputStream(System.in);26        int nextInt() throws IOException {27            int c;28            do { c = in.read(); } while (c <= 32 && c != -1);29            if (c == -1) throw new EOFException();30            int value = 0;31            while (c > 32 && c != -1) { value = value * 10 + c - '0'; c = in.read(); }32            return value;33        }34    }35    public static void main(String[] args) throws Exception {36        FastInput input = new FastInput();37        int n = input.nextInt(), q = input.nextInt();38        int[] values = new int[n];39        for (int i = 0; i < n; i++) values[i] = input.nextInt();40        SparseTable table = new SparseTable(values);41        StringBuilder out = new StringBuilder();42        for (int i = 0; i < q; i++) {43            int l = input.nextInt() - 1, r = input.nextInt() - 1;44            out.append(table.query(l, r)).append('\n');45        }46        System.out.print(out);47    }48}

Hints

Hint 1

Precompute blocks whose lengths double at each level.

Hint 2

Cover a query from both ends using its largest fitting power of two.

Hint 3

Overlapping minima are safe because min is idempotent; use right-width+1 as the second start.

Edge Cases

A one-element interval uses k=0 and the same cell twice.
A power-of-two length uses identical blocks, which must not cause double-counting concerns for min.
A full-array query can have a non-power-of-two length and therefore overlap.
Repeated minima are harmless, including inside the overlap.

Common Mistakes and Interview Tips

Using length right-left instead of right-left+1 fails singleton queries.
Forgetting to subtract one from each CSES endpoint shifts every query.
Using this overlapping formula for sums counts the overlap twice.
Assuming a point update changes only logarithmically many cells confuses Sparse Tables with Segment Trees.

Key Takeaway

Preprocessing can remove query work when the data is static. Overlap is safe for idempotent operations such as min, max and gcd; it is unsafe for addition without a different query decomposition.