Skip to content

Sparse table

How two power-of-two blocks answer a range minimum query on a fixed array, and why summing those blocks counts some values twice.

A sparse table is a data structure that precomputes summaries of contiguous blocks of lengths 1, 2, 4, 8 and so on in a fixed array. For range minima, it uses two stored values to answer any nonempty interval query in constant time once the endpoints are known. A quant researcher can use it to retrieve the lowest bar low in many different windows of the same frozen price history. Bender and Farach-Colton, The LCA Problem Revisited, §3.

Build from adjacent halves, query from both ends

Use zero-based, half-open ranges [l,r)[l,r), including ll and excluding rr. At level kk, store the minimum Tk,iT_{k,i} of each valid block [i,i+2k)[i,i+2^k). Level zero stores the individual values T0,i=aiT_{0,i}=a_i. Each longer block is two adjacent halves, so for k≥1k\ge1 the build uses

Tk,i=min⁡ ⁣(Tk−1,i, Tk−1,i+2k−1).T_{k,i}=\min\!\left(T_{k-1,i},\,T_{k-1,i+2^{k-1}}\right).
For a query of length d=r−l>0d=r-l>0, choose the largest power of two p=2kp=2^k with p≤dp\le d. Read the length-pp block starting at ll and the length-pp block ending at rr. Since p≤d<2pp\le d<2p, the two blocks stay inside the query and leave no gap. They coincide when d=pd=p. The result is min⁡(Tk,l,Tk,r−p)\min(T_{k,l},T_{k,r-p}). Erickson, Range-Minimum Queries, §1.1, “Sparse Lookup Table”.

For the fictional bar lows (8,3,7,5,2,9)(8,3,7,5,2,9) USD, the query [1,6)[1,6) has five values, so p=4p=4. The blocks [1,5)[1,5) and [2,6)[2,6) both have minimum 2 USD. The same 2 USD low at index 4 appears in both blocks, and min⁡(2,2)=2\min(2,2)=2.

![For fictional USD bar lows, query [1, 6) is covered by [1, 5) and [2, 6). Both minima are 2. The shared indices 2 through 4 contribute 14 twice, so adding the block sums gives 40. Disjoint blocks [1, 5) and 5, 6) sum to 26.
Aligning both covers to the same index shows which observations each method counts.

When overlap changes the answer

Minimum is associative, so it can be grouped into blocks, and idempotent, so combining a summary with itself leaves it unchanged. The two blocks put the shared portion next to itself when combined from left to right. Associativity lets you group those two copies, and idempotence reduces them to one. Maximum works for the same reason.
Addition is associative, so the same build can store sums. But adding the two overlapping block totals gives 17+23=4017+23=40, while the direct sum is 26. The shared indices 2 through 4 contribute an extra 7+5+2=147+5+2=14. For an associative operation such as addition, you can instead partition the query from left to right using the powers of two in its length. Here 5=4+15=4+1, giving [1,5)[1,5) and [5,6)[5,6), with total 17+9=2617+9=26. That disjoint method uses at most O(log⁡n)O(\log n) blocks. For static sums alone, prefix sums give constant-time queries by subtraction.

What the speed assumes

For an array of length nn, each of O(log⁡n)O(\log n) levels holds at most nn entries and each entry takes constant time to form. This gives O(nlog⁡n)O(n\log n) build time and storage. The minimum query uses two lookups and one comparison, with k=⌊log⁡2d⌋k=\lfloor\log_2 d\rfloor obtained in constant time from a precomputed table of lengths. The query bound starts with array indices. When requests arrive as timestamps, the application first has to locate those endpoints in a sorted time index. Erickson, Range-Minimum Queries, §1.1 and footnote 2.
A correction can invalidate every stored block that includes the changed bar. A single level can have a linear number of overlapping blocks through a central index. If historical values change frequently, a segment tree supports point updates and range minima in O(log⁡n)O(\log n) time per operation. The SelfMadeQuant lesson Tabular and Time-Indexed Data covers timestamp validation and the different aggregation rules for lows and volume. The preview is public and the full lesson requires membership.

Sources

Last updated
  • data structures
  • algorithms
  • range queries
  • market data
Keep connecting the ideas
← Back to the glossaryBack to top ↑