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^3524713682241136211111

The table is built. Query the minimum of indices 2 to 6, 5 values, in O(1): pick the largest power of two that fits in 5, then read two windows of that length, one starting at 2 and one ending at 6. They may overlap, and for a minimum that does no harm.

Check your understanding

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

  1. The range has 5 values. Which row answers it?

    • 2^2
    • 2^3
    • 2^1

    Answer: 2^2. The row is the largest power of two that does not exceed the length.

  2. The two windows give 1 and 1. What is the minimum of indices 2 to 6?

    • 1
    • 8

    Answer: 1. Two overlapping windows cover the range, and min is idempotent, so their minimum is the answer.

How it runs, step by step

  1. The table is built. Query the minimum of indices 2 to 6, 5 values, in O(1): pick the largest power of two that fits in 5, then read two windows of that length, one starting at 2 and one ending at 6. They may overlap, and for a minimum that does no harm.

    Range minimum query from 2 to 6.

  2. 5 values fit a window of length 4 = 2^2 and not of 8, so k = 2: use row 2^2.

    Use row 2^2.

  3. Window one starts at 2 and covers 2 to 5: row 2^2, column 2 holds 1. Window two ends at 6, so it starts at 6 - 4 + 1 = 3: column 3 holds 1. They overlap on the green cells 3 to 5, counted twice, harmless for a minimum. Answer: min(1, 1) = 1.

    Minimum of 1 and 1 is 1.

  4. Minimum 1, found with two table lookups. This works for any idempotent operation such as min, max or gcd, where overlap is harmless; for sums the overlap would double-count, so a sum query needs prefix sums or a Fenwick tree instead.

    Range minimum is 1.

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