Sparse Table Range Minimum Query
Answer static range minima by overlapping two precomputed power-of-two blocks.
Free theory articleAnswer static range minima by overlapping two precomputed power-of-two blocks.
Concept & interpretation
The Range Minimum Query (RMQ) problem asks for the minimum element within a specified inclusive sub-array range [L, R]. A Sparse Table answers these static queries in constant O(1) time after an O(N log N) preprocessing step.
Experiment
Interact with the Sparse Table Range Minimum Query module to visualize the overlapping blocks:
- Select the Mixed array.
- Set the Left index to 1.
- Set the Right index to 4.
- Observe the canvas: it highlights the range [1, 4] and explicitly draws the two overlapping power-of-two blocks beneath the array.
- Note the results: Status is Valid, Minimum is 0, Earliest index is 3, and the Block exponent is 2.