Sparse Table
A sparse table is a data structure designed for static arrays (no updates after construction) that answers range minimum or range maximum queries in O(1) t...
Preprocessing for Lightning-Fast Range Queries
A sparse table is a data structure designed for static arrays (no updates after construction) that answers range minimum or range maximum queries in O(1) time after an O(N log N) preprocessing step. It exploits the observation that any range [L, R] can be covered by two overlapping powers-of-two-length intervals. Since minimum and maximum are idempotent operations (overlapping does not change the answer), covering with overlapping intervals is valid.
The sparse table is a two-dimensional array where table[i][j] stores the minimum (or maximum) of the subarray starting at index i with length 2 to the power of j. The table has N rows and floor(log base 2 of N) plus one columns, giving O(N log N) entries and O(N log N) space.
Build the table bottom-up: for j equals zero, table[i][0] equals array[i] (each single element is its own range minimum). For each subsequent j, table[i][j] equals the minimum of table[i][j minus one] and table[i plus 2 to the (j-1)][j minus one]. Each entry is computed from two previously computed entries, so the entire table fills in O(N log N) time.
O(1) Query Using Overlap
To answer a range minimum query for [L, R]: compute k equals floor(log base 2 of (R minus L plus one)). The answer is the minimum of table[L][k] and table[R minus 2 to the k plus one][k]. These two intervals of length 2 to the k together cover [L, R] with possible overlap, and since minimum is idempotent, the overlap does not distort the result.
The floor of log base 2 can be precomputed for all values from one to N in O(N) time by the recurrence log[1] equals 0 and log[i] equals log[i divided by 2] plus one. With this lookup table, each query is truly O(1): two array lookups and one comparison.
This makes sparse tables the preferred structure for static range minimum or maximum queries where queries vastly outnumber construction. Applications include Lowest Common Ancestor algorithms (by reducing LCA to range minimum on Euler tour depths) and algorithms that solve string problems via LCP (longest common prefix) arrays.
Worked Example and Limitation
Worked example: given array [2, 4, 3, 1, 6, 7, 8, 9], build a sparse table for range minimum. table[i][0] equals array[i] for all i. table[0][1] equals min(table[0][0], table[1][0]) equals min(2,4) equals 2. table[2][1] equals min(3,1) equals 1. table[0][2] equals min(table[0][1], table[2][1]) equals min(2,1) equals 1. Query minimum from index 2 to 7: R minus L plus one equals 6, k equals floor(log2(6)) equals 2. Answer equals min(table[2][2], table[4][2]) equals min(1, 6) equals 1. Correct: minimum of [3,1,6,7,8,9] is 1.
The critical limitation of sparse tables is that they do not support updates. Adding or removing an element requires rebuilding the entire table from scratch in O(N log N) time. For dynamic arrays with updates, a segment tree is the appropriate choice. Sparse tables are exclusively for read-only or static datasets.
Interview tip: if an interviewer presents a problem with range minimum queries on a fixed array and emphasizes that query speed is critical, immediately propose a sparse table for O(1) queries. If updates are present, pivot to a segment tree. Demonstrating the ability to select the right tool for constraints is a hallmark of strong algorithmic thinking.