Sparse table for fast range queries

A sparse tablesparse tableA precomputed table for answering idempotent range queries (minimum, maximum, gcd) in constant time after O(N log N) preprocessing.In the glossary answers range queries in constant time, after O(N log N) preprocessing. It only works for a query that is idempotent, meaning combining a range with part of itself again does not change the answer. Minimum, maximum, and gcd are idempotent this way; sum and product are not, since counting an element twice changes a sum but never changes a minimum.

Why this is fast, and its trade-off

Once built, the table never needs updating, and every query is a direct lookup, no recursion and no tree to descend. That makes a sparse table an easy choice whenever a problem asks many queries but never changes the underlying array.

The idempotence requirement is what makes this possible. min(min(a, b), min(b, c)) equals min(a, b, c), since including b twice changes nothing. sum(sum(a, b), sum(b, c)) is not sum(a, b, c), since b gets counted an extra time. A segment tree handles both cases; a sparse table only handles the first.

Building the table

table[i][j] holds the query result for the range starting at position i and spanning $2^j$ elements. The first column, table[i][0], is just arr[i], a range of one element.

Every later column combines two ranges of half the width: table[i][j] combines table[i][j - 1], the range [i, i + 2^{j-1}), with table[i + 2^{j-1}][j - 1], the range that starts exactly where the first one ends. Since $2^{j-1} + 2^{j-1} = 2^j$, the combined range is [i, i + 2^j), twice the width of what either half covered on its own. Filling one column takes $O(n)$, and there are $O(\log n)$ columns, for $O(n \log n)$ overall.

Answering a query

A query range does not usually line up with a power of 2. Find the largest power of 2, $2^j$, that fits inside the query's length, then cover the range with two overlapping windows of that size: one starting at the query's left end, and one ending at the query's right end. Both windows are already precomputed table entries, and since the operation is idempotent, the overlap between them changes nothing.

A worked example

Build a sparse table for range-minimum queries on [5, 3, 7, 1, 4, 2, 6], 7 elements.

Column 0 (ranges of size 1) is the array itself: table[0][0] = 5, table[1][0] = 3, table[2][0] = 7, table[3][0] = 1, table[4][0] = 4, table[5][0] = 2, table[6][0] = 6.

Column 1 (ranges of size 2) combines adjacent pairs: table[0][1] = min(5, 3) = 3, table[1][1] = min(3, 7) = 3, table[2][1] = min(7, 1) = 1, table[3][1] = min(1, 4) = 1, table[4][1] = min(4, 2) = 2, table[5][1] = min(2, 6) = 2.

Column 2 (ranges of size 4) combines pairs from column 1: table[0][2] = min(3, 1) = 1, table[1][2] = min(3, 1) = 1, table[2][2] = min(1, 2) = 1, table[3][2] = min(1, 2) = 1.

1import sys2
3
4def main() -> None:5    data = sys.stdin.read().split()6    idx = 07    n = int(data[idx])8    idx += 19    arr = list(map(int, data[idx:idx + n]))10    idx += n11    l, r = int(data[idx]), int(data[idx + 1])  # query range [l, r], inclusive12
13    # k columns are enough to cover ranges up to size n; n.bit_length() gives14    # the smallest k with 2^k > n, one more than actually needed, which is15    # a harmless extra column.16    k = n.bit_length()17
18    # table[i][j] = min of the range [i, i + 2^j)19    table = [[0] * k for _ in range(n)]20
21    for i in range(n):22        table[i][0] = arr[i]23
24    for j in range(1, k):25        half = 1 << (j - 1)26        for i in range(n - (1 << j) + 1):27            table[i][j] = min(table[i][j - 1], table[i + half][j - 1])28
29    # Convert the inclusive query [l, r] to a half-open length.30    length = r - l + 131    j = length.bit_length() - 132    result = min(table[l][j], table[r - (1 << j) + 1][j])33    print(result)34
35
36if __name__ == "__main__":37    main()

7
5 3 7 1 4 2 6
1 5

1

To query the minimum from index 1 to 5, inclusive, the range has length 5, and the largest power of 2 that fits is 4. One window of size 4 starting at index 1 gives table[1][2] = 1. A second window of size 4 ending at index 5 starts at index 2, giving table[2][2] = 1. The minimum of the two windows is min(1, 1) = 1, matching the program's output. Querying from index 2 to 6 works the same way and also gives 1, since both overlapping windows of size 4 (table[2][2] and table[3][2]) already include the array's smallest value at index 3.

Common mistakes

Mixing up inclusive and half-open ranges is the most common error. table[i][j] always covers a half-open range [i, i + 2^j); a query given as an inclusive [L, R] needs its length computed as R - L + 1 before finding the largest power of 2 that fits, not R - L.

Another mistake is recomputing the largest power of 2 that fits inside a length on every single query, using a loop or repeated division. length.bit_length() - 1 gives the same answer in constant time, since Python 3.8's int.bit_length() is a fast built-in, and reaching for it keeps every query truly $O(1)$.

A third mistake is applying a sparse table to sum or product queries. Overlapping the two windows double-counts whatever lies in the overlap, which is exactly what idempotence is supposed to prevent, and neither sum nor product is idempotent.

Why it works, and the cost

Every query is answered by combining at most two table entries, both already computed, so a query only ever costs the two lookups and one combine. Idempotence is what makes the overlap between those two windows harmless: covering part of the range twice changes nothing about a minimum, maximum, or gcd.

Building the table costs $O(n \log n)$ time and the same in space, one entry per position per power of 2 up to $\log n$. That is worse than a segment tree's $O(n)$ build, but a sparse table's $O(1)$ query beats a segment tree's $O(\log n)$ query whenever the array never changes and queries are frequent.

When a segment tree is the better choice

A sparse table's speed comes at the cost of flexibility: since the table is built once from the original array, there is no way to update a single element without rebuilding the affected columns from scratch, which costs as much as building the whole table again. If a problem mixes point updates with range queries, reach for a segment tree instead, even though its queries cost $O(\log n)$ rather than $O(1)$. Choose a sparse table only once you have confirmed the array never changes after it is built.

Making it fast in Python

Fill the table one column at a time, computing each column entirely from the column before it, rather than recursing. int.bit_length(), available in Python 3.8, computes the largest fitting power of 2 in constant time without a loop. If the same problem needs many queries, look up the query's power of 2 once per distinct length rather than recomputing it inside the query loop.