cf.completefrontend
ADVANCED DATA STRUCTURES · ADVANCED

Sparse table

Precompute the minimum of every range whose length is a power of two, then answer any range-minimum question in O(1) with two overlapping lookups.

Time O(n log n) to build, O(1) per querySpace O(n log n)2 practice problemsStep-through picture

The idea

When an array never changes but you will ask "what is the smallest item from left to right?" many times, you can do some work up front so every question is answered instantly.

A sparse table stores, for every start index i and every power of two 2^k, the minimum of the 2^k items starting at i. Row 0 is the array itself. Row k is built from row k - 1: a block of length 2^k is two blocks of length 2^(k-1) side by side.

To answer a query, pick the largest power of two that fits in the range. Two blocks of that length, one starting at left and one ending at right, cover the whole range. They may overlap, but for a minimum that doesn't matter: counting an item twice doesn't change the smallest value.

An everyday example

A library of pre-measured strips

A surveyor measures the lowest point along a road. Instead of walking the road for every question, they prepare cards: the lowest point of every 1 km strip, every 2 km strip, every 4 km strip, and so on, from every starting kilometre. For any stretch of road, they pick two cards of the same size that together cover it, maybe overlapping in the middle, and compare the two numbers.

How the example maps to the code
In the exampleIn the code
The cards for one strip lengthtable[k]
The card starting at kilometre itable[k][i], the minimum of nums[i] to nums[i + 2^k - 1]
Picking the biggest card that fitsk = Math.floor(Math.log2(right - left + 1))
Comparing the two cardsMath.min(table[k][left], table[k][right - (1 << k) + 1])

From the slow way to sparse table

  1. The obvious way to answer "what is the smallest item from left to right?" is to scan the range. That's up to n steps per question, so 100,000 questions on 100,000 items can cost 10 billion steps. The opposite extreme is to store the answer for every possible range, but that's about n² / 2 answers: 5 billion numbers for 100,000 items.
  2. A minimum has a special property: looking at an item twice doesn't change it. The minimum of two ranges that overlap is still just the smaller of their two minimums. So a range doesn't need to be split into pieces that fit perfectly; any two pieces that together cover it will do, even if they overlap.
  3. Pick both pieces with the same length: the largest power of two, 2^k, that fits inside the range. One piece starts at left, the other ends at right. Because 2^k is more than half the range's length, the two pieces always meet or overlap in the middle. So we only ever need minimums of blocks whose length is a power of two: about log n lengths times n starts. For 100,000 items that's 1,568,946 numbers instead of 5 billion.
  4. Building them is quick, too. A block of length 2^k is two blocks of length 2^(k-1) side by side, so row k comes from row k - 1 with one Math.min per entry. Build the rows once, then answer every question with two lookups and one Math.min. That table is a sparse table.

How it works

  1. Row 0 of table is a copy of nums.
  2. For k = 1, 2, ... while 2^k <= n, build row k from row k - 1.
  3. table[k][i] is the smaller of prev[i] and prev[i + 2^(k-1)]: two half-length blocks side by side.
  4. To answer rangeMin(left, right), compute the range length and k, the largest power with 2^k <= that length.
  5. Return the smaller of the block starting at left and the block ending at right.

Watch it run

This picture runs the code below on a real input. Press Step to move one step at a time, or Play to watch. The highlighted line is the one that just ran. Change the input to see other cases.

Loading the picture…
See every step at onceThe same run, laid out side by side
Drawing every step…

The code

Point at a note to light up the lines it explains.

JavaScriptOpen in the code editor (opens in a new tab)
  1. function buildSparseTable(nums) {
  2. const n = nums.length;
  3. const table = [nums.slice()];
  4. for (let k = 1; 1 << k <= n; k++) {
  5. const prev = table[k - 1];
  6. const row = [];
  7. for (let i = 0; i + (1 << k) <= n; i++) {
  8. row.push(Math.min(prev[i], prev[i + (1 << (k - 1))]));
  9. }
  10. table.push(row);
  11. }
  12. return table;
  13. }
  15. function rangeMin(table, left, right) {
  16. const k = Math.floor(Math.log2(right - left + 1));
  17. return Math.min(table[k][left], table[k][right - (1 << k) + 1]);
  18. }

How fast it is

TimeO(n log n) to build, O(1) per query
Extra memoryO(n log n)

There are about log₂ n rows of up to n entries, each computed with one Math.min. A query reads two entries.

  • Best caseO(1)

    Any query, even left === right: compute k, read two entries, and take Math.min.

  • Average caseO(1)

    Any query: the range's length only changes which row is read, never how many reads.

  • Worst caseO(1)

    Even a query over the whole array is two reads. The real cost moved to the build, which is O(n log n) once.

Common mistakes

  • Using it for sums with the overlapping trick, which counts some items twice.
  • Off-by-one errors in the second block's start: it is right - 2^k + 1, so the block ends exactly at right.
  • Calling Math.log2 in a very hot loop. A small precomputed array where log[len] is Math.floor(Math.log2(len)) is faster and avoids any floating-point doubt.
  • Using a sparse table when the array changes. Every change would need an O(n log n) rebuild.

When to use it

Look for these clues in a problem:

  • The array never changes, and there are many range minimum or maximum queries.
  • You need each query in O(1), for example inside another loop.
  • The operation doesn't care about overlap: min, max, gcd, bitwise AND or OR.
  • Lowest common ancestor queries on a tree, which reduce to a range minimum over an Euler tour.

Check yourself

Answer each one in your head first, then open it.

For 7 items, how many rows does the table have, and why does it stop?

3 rows, for block lengths 1, 2, and 4. A block of length 8 doesn't fit in 7 items, so 1 << 3 <= 7 is false and the loop ends.

In rangeMin(0, 5) on the trace's numbers, which indexes are covered by both blocks?

Indexes 2 and 3. The blocks are 0..3 and 2..5.

What would go wrong if you used the same two blocks to compute the sum of indexes 0 to 5?

The overlap is counted twice: 28 + 25 = 53, but the real sum is 38. The extra 15 is 6 + 9 from indexes 2 and 3.

How many entries does row k have for n items?

n - 2^k + 1, one for each start where a block of 2^k items still fits. For 7 items, row 2 has 7 - 4 + 1 = 4 entries.

Practice problems

Stuck on one? Tuto is in the playground too, and gives you hints, never the answer.

Not started

0 of 2 solved. Solve one to earn the bronze medal, half for silver, and all of them for gold.

Start practicing

medium

Go further

You don't need these to start practicing. Open one when you want more.

Why it works

The reasoning that makes it always right

The table keeps one property: table[k][i] is the minimum of the 2^k items from nums[i] to nums[i + 2^k - 1]. Row 0 is a copy of nums, so it holds. For k >= 1, the block splits into a left half starting at i and a right half starting at i + 2^(k-1), both of length 2^(k-1). Their minimums are already in row k - 1, because rows are built in order, so the smaller of the two is the block's minimum.

A query covers its range exactly. With len = right - left + 1 and k the largest number with 2^k <= len, both blocks fit inside the range: one starts at left, the other ends at right. And since 2^(k+1) > len, the two blocks together are longer than the range, so there is no gap between them. Every item of the range is in at least one block, and no item outside it is.

The overlap doesn't matter for a minimum, because the smallest value in the range is in one of the two blocks, so it is the smaller of the two block minimums. This works for any operation where repeating an item changes nothing: min, max, gcd, bitwise AND and OR. It does not work for sums. The array never changes, so the table stays correct forever.

Going deeper

3 more ideas

Why two blocks are enough

With k chosen as the largest power of two not above the length, 2^k is at least half the length. So a block of 2^k items starting at left and another ending at right together reach every index in between. They may overlap, and for a minimum, looking at an item twice is harmless.

Cost

There are about log n rows with up to n entries each, so building takes O(n log n) time and space. Each query is two lookups and a Math.min: O(1). If the array changes, the table must be rebuilt, so use a segment tree when there are updates.

When overlap is not allowed

For sums, counting the overlap twice gives a wrong answer. You can still use the table by splitting the range into non-overlapping power-of-two blocks (like the binary digits of the length), which costs O(log n) per query. For plain sums, a prefix-sum array is simpler.

Work it by hand

Every step in a table, with why

Build the table for 7 numbers, then answer four range-minimum questions. Each row is one row built or one query answered.

nums = [5, 8, 6, 9, 3, 7, 4], then rangeMin for (0, 2), (0, 5), (2, 6), (6, 6)

StepStepkValues comparedResultWhy
1row 00copy of nums[5, 8, 6, 9, 3, 7, 4]Blocks of length 1 are the items themselves.
2row 11prev[i] and prev[i + 1][5, 6, 6, 3, 3, 4]Each entry is the smaller of two neighbors. A block of 2 must end inside the array, so only starts 0 to 5 exist.
3row 22prev[i] and prev[i + 2][5, 3, 3, 3]Each block of 4 is two blocks of 2 from row 1. For example, table[2][1] is Math.min(6, 3) = 3, the minimum of 8, 6, 9, 3.
4row 3?31 << 3 = 8 > 7stopA block of 8 doesn't fit in 7 items, so the loop ends with 3 rows.
5rangeMin(0, 2)1table[1][0] = 5, table[1][1] = 65Length 3, so k = 1. Blocks 0..1 and 1..2 overlap at index 1.
6rangeMin(0, 5)2table[2][0] = 5, table[2][2] = 33Length 6, so k = 2. Blocks 0..3 and 2..5 overlap at indexes 2 and 3. The second block holds the 3.
7rangeMin(2, 6)2table[2][2] = 3, table[2][3] = 33Length 5, so k = 2. Blocks 2..5 and 3..6 overlap a lot, and both contain the 3 at index 4. Counting it twice is harmless.
8rangeMin(6, 6)0table[0][6] = 4, twice4Length 1, so k = 0, and both blocks are the same single item.

The answers are 5, 3, 3, and 4. The build made 3 rows with 7 + 6 + 4 = 17 entries, and every query read exactly two of them, whatever its length.

Compared with other ways

When to pick something else
ApproachTimeExtra memoryChoose it when
Sparse tableO(1)O(n log n)Per query, after an O(n log n) build. Pick it for many min or max queries on an array that never changes.
Segment treeO(log n)O(n)The array changes between queries, or memory is tight. Each update costs O(log n) instead of a full rebuild.
Scan the rangeO(n)O(1)Only a few queries, or short ranges. No setup at all.
Table of every rangeO(1)O(n²)Only for a few hundred items. It uses far more memory than a sparse table for the same O(1) queries.

Extra memory: O(n log n): about log₂ n rows of up to n entries. For 1,000 items that is 10 rows with 8,987 entries.

How the steps grow

1101001k10k100k1M116324864input size n
Steps as the input grows, for Sparse table and the other approaches, on a scale where each line up is 10 times more steps.
  • Sparse table, Table of every range O(1)
  • Segment tree O(log n)
  • Scan the range O(n)
About how many steps for bigger inputs
Approachn = 10n = 1,000n = 1,000,000
Sparse table111
Segment tree31020
Scan the range101,0001 million
Table of every range111

Inputs that need care

5 tricky inputs
left === right
The length is 1, so k = 0, and both reads are table[0][left]. It returns the item itself.
left > right, such as rangeMin(table, 4, 2)
The length is -1, Math.log2(-1) is NaN, so table[k] is undefined and reading it throws a TypeError. Check the bounds, or swap them, before calling.
right past the end, such as rangeMin(table, 1, 7) with 7 items
The second block reads past the end of its row and gets undefined, so the answer is NaN. There is no bounds check in the code.
An empty array
The build returns [[]], and any query returns NaN. Don't query an empty table.
Lengths that are exact powers of two, such as rangeMin(table, 0, 3)
Then 2^k equals the length, and the two blocks are the same block. The answer is still right; Math.log2 gives exact results for powers of two.

Variations and follow-ups

Twists interviewers add

Range maximum, gcd, AND, OR

Swap Math.min for Math.max, a gcd function, or & and |. All of these give the same result when an item is counted twice, so the two overlapping blocks still work.

Store the index of the minimum

Keep the index of the smallest item in each block instead of its value, and compare nums at those indexes. The lowest common ancestor of two tree nodes is the node with the smallest depth between their positions in an Euler tour, a list of nodes in the order a depth-first walk visits them, so it becomes this exact query.

A precomputed log table

Build log with log[1] = 0 and log[i] = log[i >> 1] + 1, then use k = log[right - left + 1]. It avoids calling Math.log2 in a hot loop and any doubt about floating-point rounding.

Sums without overlap

For an operation like sum, split the range into non-overlapping power-of-two blocks, one per 1 bit of its length, and add their sums. That works but costs O(log n) per query, so a prefix-sum array is simpler for plain sums.

In an interview

Spot it, explain it, answer follow-ups
  • Spot it from "the array doesn't change" plus "many range min or max questions", or from lowest common ancestor questions, which reduce to range minimum.
  • Explain the one idea that makes it work: overlap is harmless for min, so two equal power-of-two blocks, one from each end, always cover the range.
  • Test a one-item range, a range whose length is a power of two, and a range one longer than a power of two, like length 5. That checks the second block's start, right - (1 << k) + 1.
  • The usual follow-up is "what if items change?". Answer: one change can affect about log n entries in every row, so updates are slow; switch to a segment tree.
  • Another is "can it do range sums?". Answer: not with overlapping blocks, since overlap counts items twice. Use a prefix-sum array, or non-overlapping blocks in O(log n).

Where frontend code uses it

The same idea in real UI code
  • Chart libraries that let you zoom into a fixed dataset can show the minimum and maximum of the visible range instantly by precomputing a sparse table once.
  • Finding the lowest common ancestor of two DOM-like tree nodes many times can be done with an Euler tour plus a range-minimum sparse table.
  • Performance trace viewers summarize fixed recordings (say, the slowest frame in a selected time range) and can precompute tables like this for instant answers.

Related algorithms