Sparse table

For the smallest value in a range there is no subtraction to undo a prefix. But if the list never changes, a table of the minimum of every block whose length is a power of two answers any range with just two reads.

The smallest value in a range

The question: given a list that never changes, what is min(a[l:r])? Many questions are of this kind, often called RMQ (range minimum query): the lowest price in a period, the shallowest point between two places, and, inside other algorithms, the lowest common ancestor of two tree nodes (STRG uses it with suffix arrays).

min(a[l:r]) in Python costs O(r − l). Storing the answer for every pair (l, r) answers in O(1), but there are about n² / 2 (n times n, halved) pairs: for a million values, half a million million answers. The sparse table stores only n log₂ n of them and still answers in O(1).

The table

A power of two is 1, 2, 4, 8, …: some number k of twos multiplied together (and 2⁰ is 1), written 2^k. Row k of the table holds, for every start i, the minimum of the block of length 2^k that starts at i.

• Row 0 is the list itself (blocks of length 1).
• Each block of row k is two blocks of row k − 1 side by side, so its minimum is the smaller of their two minimums: row k at i is the smaller of row k − 1 at i and at i + h, where h is half the block length.

There are about log₂ n rows of at most n entries, each found with one comparison, so the build costs O(n log n) time and memory. For a million values that is 20 million entries: a lot for Python lists, but fine for a few hundred thousand.

Answering with two blocks

For a range of length L = r − l, take the largest power of two that fits: 2^k ≤ L. Two blocks of that length cover the range: one that starts at l, and one that ends at r − 1, so it starts at r − 2^k. Since 2 · 2^k > L, together they leave no gap. They may overlap, and that does not matter:

A value in both blocks is counted twice, and a minimum does not care: min(x, x) = x. Python gives k directly: (r - l).bit_length() - 1 is the position of the highest 1 bit of the length, which is ⌊log₂ L⌋ (log₂ rounded down). So a question costs two reads and one comparison: O(1).

def build(a):
    t = [a[:]]
    k = 1
    while 1 << k <= len(a):
        prev, h = t[-1], 1 << (k - 1)
        t.append([min(prev[i], prev[i + h])
                  for i in range(len(a) - (1 << k) + 1)])
        k += 1
    return t

def query(t, l, r):          # min of a[l:r], with l < r
    k = (r - l).bit_length() - 1
    return min(t[k][l], t[k][r - (1 << k)])

1 << k is 2^k: the bit 1 moved k places to the left. Row k has n − 2^k + 1 entries, one per block that fits.

Which operations work

The overlap method needs an operation where repeating a value changes nothing. Such an operation is called idempotent:

• minimum and maximum;
• greatest common divisor (MATH): gcd(x, x) = x;
• bitwise and, bitwise or.

Sums are not idempotent: an overlapping value would be counted twice. A sparse table can still answer a sum by splitting the range into blocks that do not overlap, one per 1 bit of the length, in O(log n), but prefix sums already do it in O(1).