How does a Sparse Table enable O(1) Range Minimum Queries?
ā Interview Prompt: Explain Sparse Table construction O(N log N), O(1) idempotent range queries (min/max/GCD), and overlap of power-of-two intervals.
A Sparse Table preprocesses an array for $O(1)$ range minimum/maximum queries using the idempotency of min/max:
$\min(a, a) = a$ ā overlapping intervals don't double-count.
Construction: $O(N \log N)$
sparse[i][j] = minimum in range $[j, j + 2^i - 1]$.
sparse[i][j] = min(sparse[i-1][j], sparse[i-1][j + 2^(i-1)])
Query: $O(1)$
For range $[l, r]$, let $k = \lfloor \log_2(r - l + 1) \rfloor$:
RMQ(l, r) = min(sparse[k][l], sparse[k][r - 2^k + 1])
Two overlapping intervals of length $2^k$ cover $[l, r]$ ā valid due to idempotency.
Code Implementation Example
class SparseTable {
private table: number[][];
private log2: number[];
constructor(arr: number[]) {
const n = arr.length;
const LOG = Math.floor(Math.log2(n)) + 1;
this.log2 = new Array(n + 1).fill(0);
for (let i = 2; i <= n; i++) this.log2[i] = this.log2[i >> 1] + 1;
this.table = Array.from({ length: LOG }, () => new Array(n).fill(0));
this.table[0] = [...arr];
for (let j = 1; j < LOG; j++) {
for (let i = 0; i + (1 << j) <= n; i++) {
this.table[j][i] = Math.min(
this.table[j - 1][i],
this.table[j - 1][i + (1 << (j - 1))]
);
}
}
}
query(l: number, r: number): number { // O(1)
const k = this.log2[r - l + 1];
return Math.min(this.table[k][l], this.table[k][r - (1 << k) + 1]);
}
}Sparse Table achieves O(1) queries for idempotent functions (min, max, GCD) via overlapping power-of-2 intervals. Not suitable for sum queries (use Fenwick or Segment Tree).