AlgoScope

Sparse Table

structureintermediateTime O(1) querySpace O(n log n)

If the array never changes, why answer each range minimum from scratch? A sparse table precomputes the minimum of every window whose length is a power of two, which is only n log n numbers, and each row comes straight from the row above by combining two half-length windows. Any range can then be covered by two windows of the largest power of two that fits, one pushed against each end. They overlap, but a minimum counted twice is still the minimum, so the answer is one comparison. The same trick works for max and gcd; it fails for sums, where the overlap would double-count.

012345672^02^12^22^352471368

Build a sparse table of minimums over 5, 2, 4, 7, 1, 3, 6, 8. Row 2^k, column i will hold the minimum of the window of length 2^k starting at i. Row 2^0 is the values themselves; every other row comes from the row above, so the whole table costs O(n log n) and no cell looks at more than two others.

Check your understanding

The player pauses before each decision in this run and asks what happens next. Here are all 3, with their answers.

  1. Row 2^1, column 0 combines 5 and 2 from the row above. What goes there?

    • 2
    • 5
    • 8

    Answer: 2. Each cell is the minimum of the two half-length windows that tile it.

  2. Row 2^2, column 0 combines 2 and 4 from the row above. What goes there?

    • 2
    • 4
    • 8

    Answer: 2. Each cell is the minimum of the two half-length windows that tile it.

  3. Row 2^3, column 0 combines 2 and 1 from the row above. What goes there?

    • 1
    • 2
    • 8

    Answer: 1. Each cell is the minimum of the two half-length windows that tile it.

How it runs, step by step

  1. Build a sparse table of minimums over 5, 2, 4, 7, 1, 3, 6, 8. Row 2^k, column i will hold the minimum of the window of length 2^k starting at i. Row 2^0 is the values themselves; every other row comes from the row above, so the whole table costs O(n log n) and no cell looks at more than two others.

    Building a sparse table over 8 values with 4 rows.

  2. Row 2^1 covers windows of length 2. Cell 0 is the minimum of two windows of length 1 from the row above: 5 at column 0 and 2 at column 1, so min = 2. Together they are exactly the values from index 0 to 1.

    Row 2^1, column 0: min of 5 and 2 is 2.

  3. The rest of row 2^1 the same way: column i is min(row 2^0 at i, row 2^0 at i + 1), up to column 6, the last window of length 2 that fits in 8 values. 7 windows in this row.

    Row 2^1 filled: 2, 2, 4, 1, 1, 3, 6.

  4. Row 2^2 covers windows of length 4. Cell 0 is the minimum of two windows of length 2 from the row above: 2 at column 0 and 4 at column 2, so min = 2. Together they are exactly the values from index 0 to 3.

    Row 2^2, column 0: min of 2 and 4 is 2.

  5. The rest of row 2^2 the same way: column i is min(row 2^1 at i, row 2^1 at i + 2), up to column 4, the last window of length 4 that fits in 8 values. 5 windows in this row.

    Row 2^2 filled: 2, 1, 1, 1, 1.

  6. Row 2^3 covers windows of length 8. Cell 0 is the minimum of two windows of length 4 from the row above: 2 at column 0 and 1 at column 4, so min = 1. Together they are exactly the values from index 0 to 7.

    Row 2^3, column 0: min of 2 and 1 is 1.

  7. 4 rows, 21 cells, each computed from two cells above: O(n log n) time and space. From now on any range minimum is two lookups, but a changed value would invalidate up to log n rows, so the table suits arrays that never change.

    Sparse table built with 21 cells.

Remember

  • table[k][i] is the minimum of the window of length 2^k starting at i, built as min(table[k-1][i], table[k-1][i + 2^(k-1)]).
  • Query [l, r]: k = floor(log2(r - l + 1)); answer = min(table[k][l], table[k][r - 2^k + 1]).
  • Only for idempotent operations on static arrays: overlap must be harmless and an update would rewrite log n rows.

Topics covered

Related

Where this is used

Text indexingSuffix arrays and the LCP array

The longest common prefix of any two suffixes in a suffix array is the minimum of the LCP array over the span between their positions, so counting occurrences of a pattern or finding the longest repeated substring becomes a range minimum. The LCP array is built once during indexing and then never changes while the index is served, and a full-text index answers vastly more queries than it has entries, which is exactly the trade an n log n precompute is designed for. SDSL-lite ships rmq_support_sparse_table, a plain sparse table, alongside its succinct alternatives, for exactly this job next to an LCP array.

Graph queriesLowest common ancestor on a fixed tree

Flatten a tree with an Euler tour and the lowest common ancestor of two nodes is the shallowest entry between their two positions, turning an ancestry question into a range minimum over a static array. KACTL, the contest library from KTH, does precisely that: LCA.h walks the tree once to build the Euler array, hands it to the sparse table in RMQ.h, and every later ancestor query is one comparison. That is the shape the structure wants, a tree fixed before the first query and queried far more often than it has nodes. The same doubling shows up without the Euler tour as binary lifting, where up[k][v] is the 2^k-th ancestor of v and row k is built from row k - 1 the way this table is, giving O(log n) queries instead of O(1) but answering k-th ancestor directly.

AudioWaveform overview files

Drawing one pixel column of a waveform means taking the minimum and maximum over a range of samples, and that range changes with every zoom and scroll. Audacity precomputes min/max summaries when audio is imported, at 256 samples per block and again at 65536, so a redraw reads summaries instead of millions of raw samples; other editors call the same thing a peak file. It is this table cut down to two levels rather than log n, because a screen only has a handful of useful zoom scales, and min and max are what make it safe for a summary block to spill past the visible range.

DatabasesSkip indexes on immutable data

Parquet stores a min and a max per row group, and ClickHouse builds a minmax skip index per granule, so a range predicate reads the summary and discards whole blocks without decoding them. The precondition is the one this structure needs: the data is frozen once written, so a summary can never go stale, and min and max are chosen because merging two blocks costs one comparison. The difference is depth, since a single level of coarse blocks already removes most of the disk reads, and nobody pays n log n storage to have every window length available.

Why it works this way

Why not prefix minima, the way prefix sums work?

A prefix sum answers any range because subtraction undoes addition: sum(l, r) is prefix(r) minus prefix(l - 1). Minimum has no inverse, so once a 3 has been folded into a running minimum there is no way to pull it back out, and one prefix array of n values cannot answer arbitrary ranges. The sparse table buys those ranges back by storing every power-of-two window instead of every prefix, paying n log n memory for the privilege, and it only gets away with overlapping windows because min can absorb the same element twice. An operation that is neither invertible nor idempotent, matrix multiplication for instance, gets neither trick and needs a segment tree.

Getting floor(log2) right

Do not call a floating point log per query. It costs more than the single comparison it feeds, and the usual spelling log(len) / log(2) can land just below an integer, so a length of 1024 floors to 9 instead of 10. Where that wrong value lands decides the damage. If build sizes the table with it while query uses a correct integer log, the table has one row too few and a query over the whole array reads a row that was never allocated; if both use the same wrong value, a power-of-two range still tiles exactly from two halves and the bug stays invisible. Precompute an integer table once with lg[1] = 0 and lg[i] = lg[i / 2] + 1, or use a leading-zero intrinsic such as 31 - Integer.numberOfLeadingZeros(len). Any k that is one too small leaves a hole in the middle: the two windows then reach across at most 2^(k+1) positions, which covers the range only when its length is exactly that.

The rows get shorter as you go up

Row k is defined only for i from 0 to n - 2^k, because a window of length 2^k starting any later runs off the end of the array. That is why the build loop stops at n - (1 shl k) rather than n - 1; carry it to n - 1 and table[k - 1][i + 2^(k - 1)] reads past the row above. Queries never look at those cells, since k is chosen so both windows fit inside [l, r], so the structure is a triangle stored in a rectangle. The unused cells come to 2^k - 1 on row k, about 2n in total, a small tail next to the n log n you meant to allocate rather than the half the shape suggests.

What one update actually costs

Changing a single value invalidates every window containing it: up to 2^k windows on row k, which sums to about 2n entries across the whole table, so a point update is O(n) work and not O(log n). That is the real content of the word static here, and it is why a segment tree still exists despite its slower query. Read it the other way when there are no updates: a sparse table query is two reads from the same row and one comparison, with no descent and no branching, which is a much smaller constant than a segment tree can reach.

Read more

Next up