You need to answer range minimum queries on a static array. Thousands of them, maybe millions. A naive loop over each range costs O(n) per query, and with 10^6 queries on an array of size 10^5, that is 10^11 operations. Far too slow. A segment tree brings it down to O(log n) per query, which works, but what if you could answer every query in O(1) after a one-time preprocessing step?

That is exactly what a Sparse Table does. It preprocesses a static array in O(n log n) time and space, then answers range minimum (or maximum, or GCD) queries in constant time. The catch: the array cannot change. No updates allowed. But when your data is immutable, which happens more often than you might think, a Sparse Table is the fastest range query structure there is.

Sparse Tables occupy a specific but important niche in the algorithmic toolkit. Here is why they are worth learning:

The Problem

Consider the simplest approach to answering range minimum queries: for each query (l, r), iterate from index l to r and track the minimum. That is O(r - l + 1) per query, which is O(n) in the worst case. With many queries, this adds up fast.

A segment tree improves this to O(log n) per query, which is excellent for dynamic data. But if the array never changes, we are paying for update capabilities we do not need. Can we trade away update support for even faster queries?

Yes. The Sparse Table does exactly that.

The Key Insight

The core observation behind Sparse Tables is that any range of length L can be covered by at most two overlapping ranges whose lengths are powers of 2.

Here is why: for any range [l, r] of length L = r - l + 1, compute k = floor(log2(L)). The value 2^k is at least L/2. So the range [l, l + 2^k - 1] covers the first chunk, and the range [r - 2^k + 1, r] covers the last chunk. These two ranges overlap in the middle, but together they cover the entire [l, r] range.

Now here is the key: if the operation you care about is idempotent (applying it to the same element twice does not change the result), then overlapping is perfectly fine. The minimum of a set does not change if you include some elements twice. Same for maximum, GCD, bitwise AND, and bitwise OR. For these operations, you can just combine the answers from two overlapping power-of-2 ranges, and the result is correct.

So the plan is simple: precompute the answer for every possible power-of-2 range in the array, then answer any query by combining two such ranges.

The Analogy

Think of it like covering a hallway with two overlapping rugs. You have rugs in sizes 1, 2, 4, 8, 16 meters, and so on (powers of 2). No matter how long the hallway is, you can always pick a rug size that is at least half the hallway length, place one rug starting from the left end and another ending at the right end, and the two rugs together cover the entire hallway. Some floor in the middle gets covered twice, but if all you care about is "is every spot covered?" (an idempotent question), the overlap does not matter.

Visual Overview

The following diagram illustrates how a query range [2, 7] on an 8-element array is covered by two overlapping power-of-2 ranges of length 4.

Indices [4] and [5] are covered by both ranges, but since we are computing the minimum (an idempotent operation), the overlap has no effect on the result.

Building the Table

A Sparse Table is a 2D array table[i][j] where table[i][j] stores the answer (say, the minimum) for the range of length 2^j starting at index i. In other words, table[i][j] covers the range [i, i + 2^j - 1].

The build process uses dynamic programming:

The total number of entries is approximately n log2(n), and each entry takes O(1) to compute, giving an overall build time of O(n log n)*.

This is the same "combine two halves" idea that segment trees use, except we are precomputing every possible range rather than building a tree structure.

Precomputing Log Values

To answer queries in O(1), we need floor(log2(L)) for any range length L. Computing this on the fly is fine (most languages have a log function), but in competitive programming, floating-point log can introduce subtle precision errors. The standard practice is to precompute an integer log table:

This runs in O(n) and gives exact integer values.

Querying in O(1)

Given a query range [l, r]:

The first range [l, l + 2^k - 1] starts at the left boundary. The second range [r - 2^k + 1, r] ends at the right boundary. Together they cover [l, r], possibly overlapping in the middle. For idempotent operations, this overlap is harmless.

Why Overlapping Works for Min but Not Sum

This is a point that trips up many people, so let us be explicit.

For non-idempotent operations like sum, you cannot use overlapping ranges. You could still use a Sparse Table, but you would need to decompose the query range into non-overlapping power-of-2 ranges (similar to how a Fenwick Tree decomposes prefix sums). This gives O(log n) query time instead of O(1), which is no better than a Fenwick Tree or segment tree.

Let us build a Sparse Table for the array arr = [3, 1, 4, 1, 5, 9, 2, 6] (8 elements, 0-indexed) and then answer a few range minimum queries.

Step 1: Building the Table

Column j = 0 (ranges of length 1):

Each entry is just the element itself.

Column j = 1 (ranges of length 2):

Each entry combines two adjacent length-1 ranges.

Column j = 2 (ranges of length 4):

Each entry combines two length-2 ranges.

Column j = 3 (ranges of length 8):

Only one range of length 8 fits in an 8-element array.

The Complete Table

Entries marked "-" do not exist because the range would extend past the end of the array. The table has n (floor(log2(n)) + 1) = 8 4 = 32 cells, but only 22 are valid. This is consistent with the O(n log n) space claim.

Step 2: Answering Queries

Query 1: min(arr[1..6]) (range [1, 6], length 6)

We can verify: arr[1..6] = [1, 4, 1, 5, 9, 2], and the minimum is indeed 1.

Query 2: min(arr[4..7]) (range [4, 7], length 4)

Notice that when the range length is exactly a power of 2, both ranges are identical. No wasted work, just a clean lookup.

Query 3: min(arr[0..2]) (range [0, 2], length 3)

The overlap here is index 1, which is counted in both ranges. Since min is idempotent, the result is correct. arr[0..2] = [3, 1, 4], minimum is 1.

The implementation follows a simple structure, so let us walk through the logic once.

The constructor builds the table in two phases. First, the log table is precomputed using the recurrence logTable[i] = logTable[i/2] + 1. This avoids floating-point log calls during queries. Second, the sparse table itself is filled column by column. Column 0 copies the input array directly. Each subsequent column j combines entries from column j-1 using the recurrence: the range [i, i + 2^j - 1] is the minimum of [i, i + 2^(j-1) - 1] and [i + 2^(j-1), i + 2^j - 1].

The loop bound i + (1 << j) - 1 < n ensures we only compute entries for ranges that fit entirely within the array. This is a common source of off-by-one errors. The condition checks that the last index of the range (i + 2^j - 1) is a valid array index.

The query method is three lines. Compute the range length, look up k in the log table, and return the minimum of two overlapping ranges. The bit shift 1 << k computes 2^k efficiently.

Common Mistakes

1. Off-by-one in the build loop. The inner loop condition must be i + (1 << j) - 1 < n, not i + (1 << j) < n. The latter computes one fewer entry per column, silently producing wrong results for queries near the end of the array.

2. Using floating-point log for queries. Writing k = (int)(Math.log(length) / Math.log(2)) seems fine, but floating-point imprecision can produce wrong values. For example, log(8)/log(2) might return 2.9999999 instead of 3, and casting to int gives 2 instead of 3. Always use an integer log table.

3. Forgetting to handle length 1 ranges. When l == r, the length is 1, k = 0, and the query returns min(table[l][0], table[l][0]). This works correctly, but make sure your log table handles logTable[1] = 0.

4. Applying the O(1) query to non-idempotent operations. If you build a Sparse Table for sum and try to use the two-range overlap query, you will double-count elements in the overlap region. For sum queries, you must decompose into non-overlapping power-of-2 ranges.

5. Incorrect maxLog calculation. The number of columns needed is floor(log2(n)) + 1. A common error is using log2(n) without the +1, which misses the last column and causes out-of-bounds access for queries on the full array.

Time Complexity

Build: O(n log n)

The table has at most n * (floor(log2(n)) + 1) entries. Each entry is computed in O(1) from two entries in the previous column. The log table precomputation is O(n). So the total build time is O(n log n).

Query: O(1)

Each query performs one log table lookup, two table lookups, one min operation, and a few arithmetic operations. All constant time.

Space Complexity

O(n log n)

The table stores at most n (floor(log2(n)) + 1) integers. For n = 10^5, this is about 10^5 17 = 1.7 10^6 entries, roughly 6.8 MB for 32-bit integers. For n = 10^6, it is about 2 10^7 entries, roughly 80 MB. This can be tight in memory-constrained environments.

The log table adds O(n) space, which is dominated by the main table.

Comparison with Alternatives

The trade-off is clear: Sparse Table wins on query time but loses on space and requires static data. Segment trees and Fenwick trees are more flexible. Sqrt decomposition is simpler to implement but slower.

2D Sparse Table

The Sparse Table concept extends to two dimensions for answering range minimum queries on a static 2D matrix. Instead of a 2D table, you build a 4D table: table[i][j][ki][kj] stores the minimum in the submatrix from (i, j) to (i + 2^ki - 1, j + 2^kj - 1).

Build time and space are both O(n m log(n) * log(m)), and each query takes O(1) by combining four overlapping submatrices (similar to 2D prefix sum inclusion-exclusion, but with overlapping ranges).

This is rarely needed in practice, but it appears in competitive programming problems involving static 2D grids.

Non-Idempotent Operations (Sum, Product)

You can still build a Sparse Table for sum or product, but you lose the O(1) query. Instead, you decompose the query range [l, r] into non-overlapping power-of-2 ranges by looking at the binary representation of the range length.

For example, if the range length is 13 = 1101 in binary, you decompose it into ranges of length 8, 4, and 1. This gives O(log n) query time, which is no better than a segment tree. The only benefit is the simpler implementation (no tree structure to manage), but in practice, most people just use a segment tree for non-idempotent operations.

GCD Sparse Table

GCD is idempotent: gcd(a, a) = a. So the overlapping O(1) query works for range GCD queries. The implementation is identical to range minimum, just replace min with gcd. This is useful for problems like "find the GCD of all elements in a subarray" when the array is static.

Disjoint Sparse Table

The Disjoint Sparse Table is a clever variant that supports O(1) queries for any associative operation, not just idempotent ones. It works by precomputing answers for ranges that are "centered" at specific boundaries, avoiding the overlap issue entirely.

The build time and space are still O(n log n), and queries are still O(1). The trade-off is a more complex implementation. This is an advanced technique that appears in competitive programming but rarely in interviews.

Comparison of Variants

Understanding when to use a Sparse Table versus its alternatives is just as important as knowing how it works.

When to Choose Sparse Table

When NOT to Use Sparse Table

Pattern 1: Static Range Minimum Query (RMQ)

Problem type: Given a static array, answer many queries of the form "what is the minimum element in the subarray [l, r]?"

How Sparse Table helps: This is the textbook application. Build the Sparse Table once in O(n log n), then answer each query in O(1). No other data structure matches this query performance for static data.

Pattern 2: LCA via Euler Tour + RMQ

Problem type: Given a tree, answer many queries of the form "what is the Lowest Common Ancestor of nodes u and v?"

How Sparse Table helps: The classic reduction works as follows. Perform an Euler tour of the tree, recording the depth and node at each step. The LCA of u and v corresponds to the node with minimum depth between the first occurrences of u and v in the Euler tour. This is a range minimum query on the depth array. Using a Sparse Table, you get O(n log n) preprocessing and O(1) per LCA query.

Pattern 3: Sliding Window Minimum/Maximum (Static Variant)

Problem type: Given a static array and a fixed window size w, find the minimum in every window of size w.

How Sparse Table helps: Build the table once, then for each window position i, query min(arr[i..i+w-1]) in O(1). Total time: O(n log n) build + O(n) queries = O(n log n). A monotonic deque achieves O(n) for this specific problem, but the Sparse Table approach is simpler to code and generalizes to variable-width windows.

Interview Tips

Key Takeaways

Quick Reference