Sparse Table Range Minimum Query

Worked Example

Consider the Mixed array: [8, 5, 2, 0, 9, 6, 3, 7]. We precompute a table st[k][i] which stores the index of the minimum element in the block starting at i of length 2^k.

For length 2² = 4, st[2][1] covers indices 1, 2, 3, 4 (values [5, 2, 0, 9]). The minimum is 0 at original index 3.

To query the range [L=1, R=4] (length 4), we find the largest block exponent k = floor(log2(4)) = 2. We combine two overlapping blocks of length 4:

• The left block starting at L=1: st[2][1] (min index 3).
• The right block ending at R=4, which starts at R - 2² + 1 = 4 - 4 + 1 = 1: st[2][1] (min index 3).

The minimum of these two overlapping blocks is at index 3, yielding the value 0.

1. Find k.
2. Look up left block.
3. Look up right block.
4. Take minimum.

Experiment

Interact with the Sparse Table Range Minimum Query module to visualize the overlapping blocks:

1. Select the Mixed array.
2. Set the Left index to 1.
3. Set the Right index to 4.
4. Observe the canvas: it highlights the range [1, 4] and explicitly draws the two overlapping power-of-two blocks beneath the array.
5. Note the results: Status is Valid, Minimum is 0, Earliest index is 3, and the Block exponent is 2.

Limitations

The primary limitation of a Sparse Table is that it is a static data structure. Once built, the underlying array cannot be modified without completely rebuilding the O(N log N) table. If the application requires frequent updates to the array elements interspersed with range queries, a mutable structure such as a Segment Tree (which offers O(log N) updates and queries) is necessary.

Additionally, this O(1) query technique relies on the operation being idempotent, meaning min(a, a) = a. Overlapping blocks do not double-count elements for minimums or maximums, but this overlapping approach would fail for sums, where a + a = 2a.

References

• The LCA Problem Revisited - Bender and Farach-Colton (2000).

This seminal paper describes the constant-time RMQ approach using power-of-two blocks and sparse tables as a fundamental building block for solving Lowest Common Ancestor problems on trees.