Sparse tables for static range queries

A sparse table answers range questions about an array that never changes, such as “what is the smallest value between positions l and r?”, in constant time. It precomputes the minimum of every run of 1, 2, 4, 8 and so on consecutive values: entry table[k][i] holds the minimum of the 2ᵏ values that start at position i. Any range is covered by two blocks of the same length, one that starts at its left end and one that ends at its right end, so a query reads two entries and returns the smaller. The two blocks may overlap, and for a minimum that is harmless: a value seen twice is still the same minimum. Building the table takes O(n log n) time and memory. The price is that the array must stay fixed, and that sums, which would count the shared values twice, need another tool. This lesson builds a table by hand, checks it on a year of temperatures and times it against scanning every range.

The table: minimums of blocks of 1, 2, 4, 8 and so on

Level 0 of the table is the array itself, blocks of length 1. Every later level is built from the level below it, because a block of length 2ᵏ is two blocks of length 2ᵏ⁻¹ side by side: table[k][i] = min(table[k - 1][i], table[k - 1][i + 2**(k - 1)]).

Level k has n − 2ᵏ + 1 entries, one for every position where a block of that length still fits, and the levels stop at the largest k with 2ᵏ ≤ n, which is ⌊log₂ n⌋. That makes ⌊log₂ n⌋ + 1 levels of at most n entries each, so O(n log n) entries, each computed in O(1) from two entries of the level below. Over 100,000 values the table has 17 levels and 1,568,946 entries.

A query reads two overlapping blocks

For the range from l to r, both ends included, let the length be r − l + 1 and let k be the largest whole number with 2ᵏ ≤ length, that is ⌊log₂(r − l + 1)⌋. The block of length 2ᵏ that starts at l and the block that ends at r, which starts at r − 2ᵏ + 1, both lie inside the range. Together they cover it, because their lengths add up to 2ᵏ⁺¹, which is more than the length. The answer is the smaller of table[k][l] and table[k][r - 2**k + 1]: two reads and one comparison, however long the range is.

Finding k needs no floating point. In Python, (r - l + 1).bit_length() - 1 is ⌊log₂(r − l + 1)⌋, because bit_length counts the binary digits of a positive integer. In JavaScript, 31 - Math.clz32(length) gives the same for lengths below 2³¹, since Math.clz32 counts the leading zero bits of a 32-bit integer. A precomputed list with log[1] = 0 and log[i] = log[i // 2] + 1 works in any language.

Ten nights, traced

Ten nights of minimum temperatures in a hill town, in degrees Celsius (synthetic data), give a table of four levels. The program prints every level, then four queries with the two blocks each one reads:

"""A sparse table over ten nights of minimum temperatures (synthetic), built level by level, then queried."""


def build(values):
    """table[k][i] is the minimum of values[i : i + 2**k], the block of length 2**k that starts at i."""
    table = [list(values)]
    k = 1
    while 2**k <= len(values):
        below = table[k - 1]
        half = 2 ** (k - 1)
        # A block of length 2**k is two blocks of length 2**(k - 1) side by side.
        table.append([min(below[i], below[i + half]) for i in range(len(values) - 2**k + 1)])
        k += 1
    return table


def query(table, left, right):
    """The minimum of values[left .. right], both ends included, from two blocks of length 2**k."""
    k = (right - left + 1).bit_length() - 1  # floor(log2(length))
    return min(table[k][left], table[k][right - 2**k + 1])


nights = [14, 11, 13, 9, 12, 8, 10, 15, 7, 12]
table = build(nights)
print("nights 0-9:", nights)
for k, level in enumerate(table):
    print(f"level {k}, blocks of {2**k}: {level}")

for left, right in [(2, 8), (1, 5), (0, 3), (6, 6)]:
    length = right - left + 1
    k = length.bit_length() - 1
    second = right - 2**k + 1
    print(
        f"nights {left}-{right} ({length} night{'s' if length > 1 else ''}): k = {k}, "
        f"block {left}-{left + 2**k - 1} gives {table[k][left]}, "
        f"block {second}-{right} gives {table[k][second]}, "
        f"minimum {query(table, left, right)}"
    )

nights 0-9: [14, 11, 13, 9, 12, 8, 10, 15, 7, 12]
level 0, blocks of 1: [14, 11, 13, 9, 12, 8, 10, 15, 7, 12]
level 1, blocks of 2: [11, 11, 9, 9, 8, 8, 10, 7, 7]
level 2, blocks of 4: [9, 9, 8, 8, 8, 7, 7]
level 3, blocks of 8: [8, 7, 7]
nights 2-8 (7 nights): k = 2, block 2-5 gives 8, block 5-8 gives 7, minimum 7
nights 1-5 (5 nights): k = 2, block 1-4 gives 9, block 2-5 gives 8, minimum 8
nights 0-3 (4 nights): k = 2, block 0-3 gives 9, block 0-3 gives 9, minimum 9
nights 6-6 (1 night): k = 0, block 6-6 gives 10, block 6-6 gives 10, minimum 10

// A sparse table over ten nights of minimum temperatures (synthetic), built level by level, then queried.

/** table[k][i] is the minimum of values[i .. i + 2**k - 1], the block of length 2**k that starts at i. */
function build(values) {
  const table = [[...values]];
  for (let k = 1; 2 ** k <= values.length; k++) {
    const below = table[k - 1];
    const half = 2 ** (k - 1);
    const level = [];
    // A block of length 2**k is two blocks of length 2**(k - 1) side by side.
    for (let i = 0; i + 2 ** k <= values.length; i++) level.push(Math.min(below[i], below[i + half]));
    table.push(level);
  }
  return table;
}

/** floor(log2(n)) for 1 <= n < 2**31: 31 minus the number of leading zero bits. */
const log2Floor = (n) => 31 - Math.clz32(n);

/** The minimum of values[left .. right], both ends included, from two blocks of length 2**k. */
function query(table, left, right) {
  const k = log2Floor(right - left + 1);
  return Math.min(table[k][left], table[k][right - 2 ** k + 1]);
}

const nights = [14, 11, 13, 9, 12, 8, 10, 15, 7, 12];
const table = build(nights);
const list = (a) => `[${a.join(', ')}]`;
console.log(`nights 0-9: ${list(nights)}`);
table.forEach((level, k) => console.log(`level ${k}, blocks of ${2 ** k}: ${list(level)}`));

for (const [left, right] of [[2, 8], [1, 5], [0, 3], [6, 6]]) {
  const length = right - left + 1;
  const k = log2Floor(length);
  const second = right - 2 ** k + 1;
  console.log(
    `nights ${left}-${right} (${length} night${length > 1 ? 's' : ''}): k = ${k}, ` +
      `block ${left}-${left + 2 ** k - 1} gives ${table[k][left]}, ` +
      `block ${second}-${right} gives ${table[k][second]}, ` +
      `minimum ${query(table, left, right)}`,
  );
}

nights 0-9: [14, 11, 13, 9, 12, 8, 10, 15, 7, 12]
level 0, blocks of 1: [14, 11, 13, 9, 12, 8, 10, 15, 7, 12]
level 1, blocks of 2: [11, 11, 9, 9, 8, 8, 10, 7, 7]
level 2, blocks of 4: [9, 9, 8, 8, 8, 7, 7]
level 3, blocks of 8: [8, 7, 7]
nights 2-8 (7 nights): k = 2, block 2-5 gives 8, block 5-8 gives 7, minimum 7
nights 1-5 (5 nights): k = 2, block 1-4 gives 9, block 2-5 gives 8, minimum 8
nights 0-3 (4 nights): k = 2, block 0-3 gives 9, block 0-3 gives 9, minimum 9
nights 6-6 (1 night): k = 0, block 6-6 gives 10, block 6-6 gives 10, minimum 10

The query for nights 2 to 8 is the one in the diagram: seven nights, so k = 2, and the blocks 2–5 and 5–8 share night 5. The query for nights 1 to 5 reads blocks 1–4 and 2–5, which share three of their four nights, and still answers 8. When the length is itself a power of two, as for nights 0 to 3, both blocks are the same block, and a single night reads level 0, the value itself.

A year of nights

The same code works for any length. This program builds a table over a year of synthetic nights and asks for the coldest night of the year and of each quarter. Storing pairs of (temperature, night) instead of bare temperatures makes the minimum also say where it is, and when two nights are equally cold the pair with the earlier night is smaller:

"""A year of synthetic nightly minimum temperatures in a hill town: the coldest night of any stretch."""

import random


def build(values):
    """table[k][i] is the minimum of values[i : i + 2**k]."""
    table = [list(values)]
    k = 1
    while 2**k <= len(values):
        below, half = table[k - 1], 2 ** (k - 1)
        table.append([min(below[i], below[i + half]) for i in range(len(values) - 2**k + 1)])
        k += 1
    return table


def query(table, left, right):
    """The minimum of values[left .. right], both ends included."""
    k = (right - left + 1).bit_length() - 1
    return min(table[k][left], table[k][right - 2**k + 1])


def year_of_nights(seed):
    """365 nightly minimums in degrees Celsius: cold at both ends of the year, mild in the middle."""
    rng = random.Random(seed)
    return [18 - abs(night - 182) // 9 + rng.randint(-3, 3) for night in range(365)]


nights = year_of_nights(2026)
# Pairs (temperature, night): the minimum pair also says where the minimum is, and ties go to the earlier night.
table = build([(t, night) for night, t in enumerate(nights)])
entries = sum(len(level) for level in table)
print(f"{len(nights)} nights, {len(table)} levels, {entries:,} table entries")

t, night = query(table, 0, 364)
print(f"coldest night of the year: night {night}, {t} °C")
for q, (left, right) in enumerate([(0, 90), (91, 181), (182, 272), (273, 364)], start=1):
    t, night = query(table, left, right)
    print(f"quarter {q}, nights {left}-{right}: coldest is night {night}, {t} °C")

rng = random.Random(1)
agree = 0
for _ in range(1000):
    left = rng.randrange(365)
    right = rng.randrange(left, 365)
    agree += query(table, left, right)[0] == min(nights[left : right + 1])
print(f"{agree:,} of 1,000 random stretches agree with min() over a slice")

365 nights, 9 levels, 2,783 table entries
coldest night of the year: night 0, -5 °C
quarter 1, nights 0-90: coldest is night 0, -5 °C
quarter 2, nights 91-181: coldest is night 95, 6 °C
quarter 3, nights 182-272: coldest is night 265, 6 °C
quarter 4, nights 273-364: coldest is night 362, -5 °C
1,000 of 1,000 random stretches agree with min() over a slice

Night 0 and night 362 are both −5 °C, and the pairs make night 0 the answer for the whole year. The table has 9 levels and 2,783 entries for 365 nights, and the last line compares 1,000 random stretches with Python’s own min() over a slice: every answer agrees.

Which operations allow the overlap

The two blocks of a query share values whenever the length is not a power of two, and when it is, the query combines a block with itself. That is harmless only for an operation f with f(x, x) = x, called idempotent, which must also be associative, so that blocks can be grouped in any way. Minimum, maximum, the greatest common divisor and bitwise AND and OR qualify. This program builds a table for eight operations and compares every range of eight numbers with the true answer:

"""Which operations survive the overlap of a sparse-table query, checked on every range of eight numbers."""

import operator
from functools import reduce
from math import gcd

values = [12, 18, 6, 30, 24, 9, 15, 21]
n = len(values)
OPERATIONS = {
    "min": min,
    "max": max,
    "gcd": gcd,
    "and (&)": operator.and_,
    "or (|)": operator.or_,
    "sum (+)": operator.add,
    "xor (^)": operator.xor,
    "product (*)": operator.mul,
}


def build(values, op):
    """table[k][i] combines values[i : i + 2**k] with op."""
    table = [list(values)]
    k = 1
    while 2**k <= len(values):
        below, half = table[k - 1], 2 ** (k - 1)
        table.append([op(below[i], below[i + half]) for i in range(len(values) - 2**k + 1)])
        k += 1
    return table


def overlapping(table, left, right, op):
    """Two blocks of length 2**k, one from each end of the range: they overlap unless the length is 2**k."""
    k = (right - left + 1).bit_length() - 1
    return op(table[k][left], table[k][right - 2**k + 1])


def disjoint(table, left, right, op):
    """Blocks that never overlap, the largest that still fits first, combined from left to right."""
    result, blocks = None, 0
    for k in range(len(table) - 1, -1, -1):
        if left + 2**k - 1 <= right:
            result = table[k][left] if result is None else op(result, table[k][left])
            left += 2**k
            blocks += 1
    return result, blocks


ranges = [(left, right) for left in range(n) for right in range(left, n)]
print(f"{values}: {len(ranges)} ranges")
print("two overlapping blocks per range:")
for name, op in OPERATIONS.items():
    table = build(values, op)
    wrong = [(l, r) for l, r in ranges if overlapping(table, l, r, op) != reduce(op, values[l : r + 1])]
    line = f"  {name:<12} right on {len(ranges) - len(wrong)} of {len(ranges)} ranges"
    if wrong:
        l, r = wrong[0]
        line += f"; first wrong: {l}-{r} gives {overlapping(table, l, r, op)}, not {reduce(op, values[l : r + 1])}"
    print(line)

table = build(values, operator.add)
right = sum(disjoint(table, l, r, operator.add)[0] == sum(values[l : r + 1]) for l, r in ranges)
most = max(disjoint(table, l, r, operator.add)[1] for l, r in ranges)
print("disjoint blocks, largest first:")
print(f"  sum (+)      right on {right} of {len(ranges)} ranges, using at most {most} blocks per range")

[12, 18, 6, 30, 24, 9, 15, 21]: 36 ranges
two overlapping blocks per range:
  min          right on 36 of 36 ranges
  max          right on 36 of 36 ranges
  gcd          right on 36 of 36 ranges
  and (&)      right on 36 of 36 ranges
  or (|)       right on 36 of 36 ranges
  sum (+)      right on 0 of 36 ranges; first wrong: 0-0 gives 24, not 12
  xor (^)      right on 2 of 36 ranges; first wrong: 0-0 gives 0, not 12
  product (*)  right on 0 of 36 ranges; first wrong: 0-0 gives 144, not 12
disjoint blocks, largest first:
  sum (+)      right on 36 of 36 ranges, using at most 3 blocks per range

Sums fail on all 36 ranges, even on the ranges whose two blocks are the same block. A table built with + still answers sums if the query uses blocks that never overlap: take the largest block that fits at the left end, move past it and repeat. The last line of the run shows at most 3 such blocks for eight numbers, and there are never more than ⌊log₂ n⌋ + 1, so a sum costs O(log n). For a fixed array, prefix sums answer the same question in O(1) with n + 1 numbers, as the prefix sums lesson showed, so sparse tables are built for the idempotent operations.

What it costs, measured

This run builds a table over 100,000 random numbers, answers 100,000 random ranges, and scans the first 1,000 of them with min() over a slice to compare:

"""100,000 range-minimum queries on 100,000 numbers: a sparse table against scanning each range, timed."""

import random
import sys
import time


def build(values):
    """table[k][i] is the minimum of values[i : i + 2**k]."""
    table = [list(values)]
    k = 1
    while 2**k <= len(values):
        below, half = table[k - 1], 2 ** (k - 1)
        table.append([min(below[i], below[i + half]) for i in range(len(values) - 2**k + 1)])
        k += 1
    return table


def query(table, left, right):
    k = (right - left + 1).bit_length() - 1
    return min(table[k][left], table[k][right - 2**k + 1])


n = q = 100_000
rng = random.Random(42)
values = [rng.randrange(10**9) for _ in range(n)]
ranges = []
for _ in range(q):
    left, right = sorted((rng.randrange(n), rng.randrange(n)))
    ranges.append((left, right))

start = time.perf_counter()
table = build(values)
built = time.perf_counter() - start

start = time.perf_counter()
answers = [query(table, left, right) for left, right in ranges]
queried = time.perf_counter() - start

scanned_count = 1_000
start = time.perf_counter()
scanned = [min(values[left : right + 1]) for left, right in ranges[:scanned_count]]
scanning = time.perf_counter() - start

entries = sum(len(level) for level in table)
references = sum(sys.getsizeof(level) for level in table[1:])
average = sum(right - left + 1 for left, right in ranges) / q
print(f"{n:,} numbers, {q:,} random ranges of {average:,.0f} numbers on average")
print(f"table: {len(table)} levels, {entries:,} entries, {references / 2**20:.1f} MiB of lists above level 0")
print(f"build: {built * 1000:,.0f} ms")
print(f"{q:,} queries: {queried * 1000:,.0f} ms, {queried / q * 1e6:.2f} µs each")
print(f"scanning the first {scanned_count:,} ranges with min(): {scanning * 1000:,.0f} ms, "
      f"so about {scanning * q / scanned_count:,.0f} s for all {q:,}")
print(f"the first {scanned_count:,} answers agree: {scanned == answers[:scanned_count]}")

position = n // 2
touched = sum(1 for k, level in enumerate(table) for i in range(max(0, position - 2**k + 1), min(position, len(level) - 1) + 1))
print(f"the value at position {position:,} lies inside {touched:,} of the table's {entries:,} blocks")

100,000 numbers, 100,000 random ranges of 33,220 numbers on average
table: 17 levels, 1,568,946 entries, 11.4 MiB of lists above level 0
build: 95 ms
100,000 queries: 61 ms, 0.61 µs each
scanning the first 1,000 ranges with min(): 636 ms, so about 64 s for all 100,000
the first 1,000 answers agree: True
the value at position 50,000 lies inside 100,000 of the table's 1,568,946 blocks

In the recorded run the table took 95 ms to build. Its levels above level 0 took 11.4 MiB of lists, because in CPython each entry is an 8-byte reference to a number object that the levels share. The 100,000 queries took 61 ms, 0.61 µs each. Scanning took 636 ms for only 1,000 ranges of 33,220 numbers on average, so all 100,000 would take about 64 seconds, about a thousand times longer, even though min() scans in C. The last line is the catch: the value at position 50,000 lies inside 100,000 of the table’s 1,568,946 blocks, so changing it means patching about n entries, where a Fenwick tree or a segment tree changes about log₂ n.

Sparse table, prefix sums or a tree?

• Scanning each range: nothing to build, O(length) per query and O(1) per change; any operation.
• Prefix sums: O(n) to build, O(1) per query and O(n) per change; sums, counts and XOR, operations that can be undone.
• A sparse table: O(n log n) to build, O(1) per query and O(n) per change; idempotent operations such as minimum, maximum, gcd, AND and OR.
• A Fenwick tree: O(n) to build and O(log n) per query and per change; sums and other operations that can be undone.
• A segment tree: O(n) to build and O(log n) per query and per change; any associative operation.

The memory differs as much as the speed: n + 1 numbers for prefix sums, n for a Fenwick tree, 2n to 4n for a segment tree and about n log₂ n for a sparse table.

Choose a sparse table when the array is fixed, the operation is idempotent and the queries are many, for example 10⁵ or more questions about one array, or the lowest-common-ancestor queries later in this module, where it turns each query into one range minimum. When values change between queries, a Fenwick tree or a segment tree pays O(log n) per change instead of rebuilding.

Exercise: range minimums

Return the minimum of every queried range. All the tests are public, and the last one asks 200,000 questions about 200,000 numbers, which a scan of every range cannot finish in time:

def range_minimums(values, queries):
    """One answer per (left, right) query: the smallest of values[left .. right], both ends included."""
    raise NotImplementedError("write range_minimums")

import random

from rmq import range_minimums

NIGHTS = [14, 11, 13, 9, 12, 8, 10, 15, 7, 12]


def test_ten_nights():
    """the ten nights of the lesson"""
    queries = [(2, 8), (1, 5), (0, 3), (6, 6), (0, 9), (8, 9)]
    assert range_minimums(NIGHTS, queries) == [7, 8, 9, 10, 7, 7]


def test_single_value_and_no_queries():
    """one value, and a call with no queries"""
    assert range_minimums([5], [(0, 0)]) == [5]
    assert range_minimums([5, 3], []) == []


def test_negative_numbers_and_ties():
    """negative numbers, equal values and ranges at both ends"""
    values = [3, -1, -1, 4, -7, 2, -7]
    queries = [(0, 2), (1, 2), (3, 6), (5, 5), (0, 6), (0, 0), (6, 6)]
    assert range_minimums(values, queries) == [-1, -1, -7, 2, -7, 3, -7]


def test_random_against_slices():
    """300 random small cases, compared with min() over a slice"""
    rng = random.Random(7)
    for _ in range(300):
        n = rng.randint(1, 40)
        values = [rng.randint(-50, 50) for _ in range(n)]
        queries = []
        for _ in range(rng.randint(1, 30)):
            left = rng.randrange(n)
            queries.append((left, rng.randrange(left, n)))
        assert range_minimums(values, queries) == [min(values[l : r + 1]) for l, r in queries], (values, queries)


def test_two_hundred_thousand_queries():
    """200,000 queries on 200,000 numbers: prefixes, suffixes, short ranges and long ones"""
    rng = random.Random(11)
    n = 200_000
    values = [rng.randrange(-10**9, 10**9) for _ in range(n)]
    prefix, suffix = values[:], values[:]
    for i in range(1, n):
        prefix[i] = min(prefix[i - 1], values[i])
    for i in range(n - 2, -1, -1):
        suffix[i] = min(suffix[i + 1], values[i])
    queries = [(0, rng.randrange(n)) for _ in range(50_000)]
    queries += [(rng.randrange(n), n - 1) for _ in range(50_000)]
    short = []
    for _ in range(50_000):
        left = rng.randrange(n - 16)
        short.append((left, left + rng.randrange(16)))
    queries += short
    long = []
    for _ in range(50_000):
        left, right = sorted((rng.randrange(n), rng.randrange(n)))
        long.append((left, right))
    queries += long
    answers = range_minimums(values, queries)
    assert len(answers) == len(queries)
    assert answers[:50_000] == [prefix[r] for _, r in queries[:50_000]]
    assert answers[50_000:100_000] == [suffix[l] for l, _ in queries[50_000:100_000]]
    assert answers[100_000:150_000] == [min(values[l : r + 1]) for l, r in short]
    assert answers[150_000:150_200] == [min(values[l : r + 1]) for l, r in long[:200]]

/** One answer per [left, right] query: the smallest of values[left .. right], both ends included. */
export function rangeMinimums(values, queries) {
  throw new Error('write rangeMinimums');
}

import { test, assert } from 'mysmartcopilot:test';
import { rangeMinimums } from './rmq.mjs';

const NIGHTS = [14, 11, 13, 9, 12, 8, 10, 15, 7, 12];

/** A seeded generator (Park and Miller), so every run checks the same cases. */
function generator(seed) {
  let s = seed;
  return (k) => {
    s = (s * 48271) % 2147483647;
    return s % k;
  };
}

const sliceMin = (values, l, r) => {
  let m = values[l];
  for (let i = l + 1; i <= r; i++) if (values[i] < m) m = values[i];
  return m;
};

test('the ten nights of the lesson', () => {
  const queries = [[2, 8], [1, 5], [0, 3], [6, 6], [0, 9], [8, 9]];
  assert.deepEqual(rangeMinimums(NIGHTS, queries), [7, 8, 9, 10, 7, 7]);
});

test('one value, and a call with no queries', () => {
  assert.deepEqual(rangeMinimums([5], [[0, 0]]), [5]);
  assert.deepEqual(rangeMinimums([5, 3], []), []);
});

test('negative numbers, equal values and ranges at both ends', () => {
  const values = [3, -1, -1, 4, -7, 2, -7];
  const queries = [[0, 2], [1, 2], [3, 6], [5, 5], [0, 6], [0, 0], [6, 6]];
  assert.deepEqual(rangeMinimums(values, queries), [-1, -1, -7, 2, -7, 3, -7]);
});

test('300 random small cases, compared with a scan of each range', () => {
  const pick = generator(7);
  for (let t = 0; t < 300; t++) {
    const n = 1 + pick(40);
    const values = Array.from({ length: n }, () => pick(101) - 50);
    const queries = [];
    for (let j = 0, m = 1 + pick(30); j < m; j++) {
      const left = pick(n);
      queries.push([left, left + pick(n - left)]);
    }
    assert.deepEqual(rangeMinimums(values, queries), queries.map(([l, r]) => sliceMin(values, l, r)), JSON.stringify([values, queries]));
  }
});

test('200,000 queries on 200,000 numbers: prefixes, suffixes, short ranges and long ones', () => {
  const pick = generator(11);
  const n = 200000;
  const values = Array.from({ length: n }, () => pick(2000000000) - 1000000000);
  const prefix = values.slice();
  const suffix = values.slice();
  for (let i = 1; i < n; i++) prefix[i] = Math.min(prefix[i - 1], values[i]);
  for (let i = n - 2; i >= 0; i--) suffix[i] = Math.min(suffix[i + 1], values[i]);
  const queries = [];
  for (let j = 0; j < 50000; j++) queries.push([0, pick(n)]);
  for (let j = 0; j < 50000; j++) queries.push([pick(n), n - 1]);
  for (let j = 0; j < 50000; j++) {
    const left = pick(n - 16);
    queries.push([left, left + pick(16)]);
  }
  for (let j = 0; j < 50000; j++) {
    const a = pick(n);
    const b = pick(n);
    queries.push([Math.min(a, b), Math.max(a, b)]);
  }
  const answers = rangeMinimums(values, queries);
  let ok = answers.length === queries.length;
  for (let j = 0; ok && j < 50000; j++) ok = answers[j] === prefix[queries[j][1]];
  for (let j = 50000; ok && j < 100000; j++) ok = answers[j] === suffix[queries[j][0]];
  for (let j = 100000; ok && j < 150200; j++) ok = answers[j] === sliceMin(values, queries[j][0], queries[j][1]);
  assert.ok(ok, 'prefixes, suffixes, short ranges and the first 200 long ranges are all answered correctly');
});

Interview questions

Why can a sparse-table query use two overlapping blocks for a minimum but not for a sum? The two blocks of a query share the values in the middle of the range whenever its length is not a power of two, and the query always combines two blocks. For the minimum, a value that is looked at twice changes nothing, because min(x, x) = x: the smaller of the two block minimums is the minimum of their union. A sum adds the shared values twice, so the answer is too large, and even a range whose two blocks coincide comes out doubled. The property needed is idempotence, f(x, x) = x, which minimum, maximum, gcd, AND and OR have. For sums, use prefix sums on a fixed array, or combine disjoint blocks of the table in O(log n).

When is a sparse table the wrong choice for range queries? When the values change: one value lies inside about n blocks of the table, so each change costs O(n) or a rebuild in O(n log n), while a Fenwick tree or a segment tree updates in O(log n). When memory is tight: a million values need about 19 million entries, against 2 million for an iterative segment tree. And when the operation is not idempotent, such as a sum or a count, prefix sums are smaller and just as fast. It is the right choice for many queries on fixed data with minimum, maximum or gcd.

Key takeaways

• A sparse table stores the minimum of every block of length 2ᵏ: table[k][i] covers positions i to i + 2ᵏ − 1, and each level comes from two entries of the level below.
• A query uses k = ⌊log₂(r − l + 1)⌋ and returns the smaller of table[k][l] and table[k][r - 2**k + 1], in O(1).
• Building takes O(n log n) time and memory: 17 levels and 1,568,946 entries for 100,000 values.
• The overlap is safe only for idempotent operations such as minimum, maximum, gcd, AND and OR. Sums need prefix sums or disjoint blocks.
• The array must not change: one value lies inside about n blocks, so data that changes needs a Fenwick tree or a segment tree.