Sparse-table range minimum: Examples & Code

Algorithm Visualizations November 16, 2026 javascript

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.

Open the 3D visualization

Sparse-table range minimum example state preview
Preview of the example's final state. Complete values are available in the worked example and interactive timeline.

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.

  1. 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
    }
  2. 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
    }
  3. 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
    }
  4. 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
    }
  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:

Editorial and testing approach · Browse all algorithm guides

Complete JavaScript implementation

javascript
 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.