Published by Dimitris Kougioumtzis · Updated
Build the range-query structure and answer an inclusive query. Static minimum queries; updates are not supported.
Precompute minima on power-of-two intervals and answer each query with two possibly overlapping blocks.
When to use Sparse-table range minimum
Many minimum queries on an immutable array.
Choosing an alternative
Segment trees handle updates but need logarithmic query work.
Worked example: input and state changes
Example input
1,2,3,4,5 | 1,4
These checkpoints follow the actual example timeline. State details show the stored values and decisions; use the visualization to inspect every intervening step.
Step 0: Level zero stores single-value minima.
State at this checkpoint
{ "values": [ 1, 2, 3, 4, 5, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 ], "active": [], "kind": "matrix", "columns": 5 }Step 2: Build block of length 2 starting at 1.
State at this checkpoint
{ "values": [ 1, 2, 3, 4, 5, 1, 2, 0, 0, 0, 0, 0, 0, 0, 0 ], "active": [ 6 ], "kind": "matrix", "columns": 5 }Step 4: Build block of length 2 starting at 3.
State at this checkpoint
{ "values": [ 1, 2, 3, 4, 5, 1, 2, 3, 4, 0, 0, 0, 0, 0, 0 ], "active": [ 8 ], "kind": "matrix", "columns": 5 }Step 6: Build block of length 4 starting at 1.
State at this checkpoint
{ "values": [ 1, 2, 3, 4, 5, 1, 2, 3, 4, 0, 1, 2, 0, 0, 0 ], "active": [ 11 ], "kind": "matrix", "columns": 5 }Step 8: Range minimum [1,4] = 2.
State at this checkpoint
{ "values": [ 1, 2, 3, 4, 5, 1, 2, 3, 4, 0, 1, 2, 0, 0, 0 ], "active": [], "kind": "matrix", "columns": 5, "result": 2 }
Expected final state
Range minimum [1,4] = 2.
Complexity and input bounds
Family: Trees. Time complexity: O(n log n) build; O(1) query.
Space complexity: O(n log n) precomputed minima.
Working-space bounds describe algorithm state and any explicitly noted output, excluding the visualization's saved timeline. Recording frames can use more memory than running the function alone. Here n is sequence length, V and E are vertex and edge counts, and other parameters refer to the named input dimensions.
1–24 values (0–99) | left,right; indices are zero-based.
The playground validates these limits before starting. Downloaded functions are callable implementations, with parameter and output-buffer contracts in their comments; they do not all repeat the playground's input validation.
Common mistakes and limitations
Overlapping blocks work because minimum is idempotent; ordinary sums would double-count the overlap.
Further reading
For background on algorithm analysis and the JavaScript function interface:
- MIT OpenCourseWare: algorithm design and analysis foundations
- MDN: JavaScript function parameters and return values
Editorial and testing approach · Browse all algorithm guides
Complete JavaScript implementation
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 | // 1–24 values 0–99, inclusive 0 ≤ left ≤ right < n. Returns range minimum. This is a static structure without updates. Reference snippets assume validated playground inputs. Fixed scratch buffers have 256 slots. Sorting variants may use a different traversal strategy than the animation. function algorithm(a, n, left, right) { let table = Array(256).fill(0); let logs = Array(256).fill(0); for (let i = 0; i < n; i++) { table[i] = a[i]; } for (let i = 2; i <= n; i++) { logs[i] = logs[i >> 1] + 1; } let level = 1; for (let width = 2; width <= n; width <<= 1, level++) { let half = width >> 1; for (let i = 0; i + width <= n; i++) { let x = table[(level - 1) * n + i]; let y = table[(level - 1) * n + i + half]; table[level * n + i] = x; if (y < x) { table[level * n + i] = y; } } } let k = logs[right - left + 1]; let span = 1 << k; let firstValue = table[k * n + left]; let lastValue = table[k * n + right - span + 1]; if (firstValue < lastValue) { return firstValue; } return lastValue; } |
Source
This paper provides research context for sparse-table range-minimum queries and develops LCA methods beyond the playground entry.
- The LCA Problem Revisited
Michael A. Bender; Martín Farach-Colton (2000). Related research paper.