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ᵏ, written1 << kin 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 length2ᵏstarting ati. - Floor of log₂:
lg[x]= the largestkwith2ᵏ ≤ x(lg[6] = 2). - Idempotent operation: doing it twice with the same element changes nothing:
min(x, x) = x, alsomaxandgcd. Sum is not idempotent. - Overlap: two ranges share some indices.
- Binary lifting: building jumps of length
2ᵏfrom two jumps of length2ᵏ⁻¹; 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
- Sparse table or segment tree? Sparse table: static data, O(1) min/max queries. Segment tree: updates, or operations like sum.
- Why may the two blocks overlap? Because
minis idempotent: counting an element twice changes nothing. - Why is the build O(n log n)? About
log nlevels, each with up tonblocks, each computed in O(1) from the level below. - How do you find
kquickly? A precomputedlg[]table or31 - Integer.numberOfLeadingZeros(len). - 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.
- 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 atl, one ending atr: O(1). - The overlap trick works for min, max and gcd, never for sum.
- Fill the last block (
<=), end the second block atr(+ 1), and use an integer log table. - Next episode: matrix problems: rotate image, spiral order, set matrix zeroes.