Range minimum with a sparse table in Python

Why it matters

Many programs ask the same question again and again. Given a list of numbers, what is the smallest value between position 3 and position 40? A game might ask it for every player's turn. A stock tool might ask it for every day in a window. If you answer each question by looking at every item in the range, the work grows with the size of the range, and the program slows down when the questions are long and many.

A sparse table answers this kind of question very fast, on the condition that the numbers never change. You spend time once, before any question is asked, to build a table of answers for blocks of fixed sizes. After that, each question takes a few steps, and the number of steps does not depend on how long the range is.

This lesson uses only a fixed list of numbers and a query that asks for the minimum. It does not cover changing a value, and that is the reason a segment tree exists. The later lessons in this module use segment trees, which can handle changing values. Here you will see the simplest structure that answers range questions quickly.

You should know how to write a Python function, read a list, and use a for loop. The programs below use min and the int.bit_length method. Both are explained where they appear.

The problem with a plain loop

Take the list [5, 2, 8, 6, 1, 7]. The positions start at 0, so position 0 holds 5, position 1 holds 2, and so on. A query asks for the minimum of the items from position l to position r, counting both ends. The query (1, 2) covers the values 2 and 8, so the answer is 2. The query (0, 5) covers all six values, so the answer is 1.

The plain way to answer a query is a loop:

def brute_min(a, l, r):
    best = a[l]
    for i in range(l + 1, r + 1):
        best = min(best, a[i])
    return best

This code is correct. Its cost is the problem. If the range has 100,000 items, the loop looks at 100,000 items. If the program asks 100,000 such questions, it does about 10 billion comparisons. A computer can do that, but in Python it takes a very long time, and an interview or a web request may not allow it.

The sparse table reduces each query to a fixed number of steps. It pays with extra memory and extra work at the start.

The idea: blocks whose length is a power of two

A power of two is a number such as 1, 2, 4, 8, 16 and so on. Each one is 2 multiplied by itself some number of times. We write 2^k for the power of two with exponent k. So 2^0 is 1, 2^1 is 2, 2^2 is 4, and 2^3 is 8.

The sparse table stores the minimum of each block of length 2^k that starts at each position i. A block here means a run of consecutive items. We call its table entry sp[k][i]. The first index is the block length as a power, and the second index is where the block starts. The name "sparse" means that the table does not store the answer for every possible range. A table with every range would hold about n * n / 2 answers. The sparse table holds only the blocks with power-of-two lengths, which is about n answers for each length.

Take the list again, [5, 2, 8, 6, 1, 7], which has 6 items. Here are the blocks of length 1. A block of length 1 is just the item itself, so the table is the list:

• sp[0] holds 5, 2, 8, 6, 1, 7.

The blocks of length 2 start at positions 0 to 4, since a block starting at position 5 would need an item at position 6, which does not exist. Each block of length 2 is the minimum of two neighbours:

• sp[1][0] is the minimum of 5 and 2, which is 2.
• sp[1][1] is the minimum of 2 and 8, which is 2.
• sp[1][2] is the minimum of 8 and 6, which is 6.
• sp[1][3] is the minimum of 6 and 1, which is 1.
• sp[1][4] is the minimum of 1 and 7, which is 1.

The blocks of length 4 start at positions 0 to 2. Each one is the minimum of four neighbours:

• sp[2][0] covers 5, 2, 8, 6, which gives 2.
• sp[2][1] covers 2, 8, 6, 1, which gives 1.
• sp[2][2] covers 8, 6, 1, 7, which gives 1.

A block of length 8 does not fit in a list of 6 items, so the table stops at length 4.

Building the table from smaller blocks

The table does not need to look at the original list more than once for each level. A block of length 2^k is made of two blocks of length 2^(k-1), one starting at i and one starting at i + 2^(k-1). The minimum of the whole block is the smaller of the two half minimums. This gives the rule:

sp[k][i] = min(sp[k-1][i], sp[k-1][i + 2^(k-1)])

Read it in words. To get the minimum of a block of length 2^k starting at i, take the smaller of two answers already in the table: the block of half the length starting at i, and the block of half the length starting at the middle.

Check it with the example. sp[2][1] should cover positions 1 to 4, which are 2, 8, 6, 1. The two halves are positions 1 and 2 (the block sp[1][1], which is 2) and positions 3 and 4 (the block sp[1][3], which is 1). The smaller is 1, which matches.

The table is built one level at a time. Level 0 is the list. Level 1 is built from level 0. Level 2 is built from level 1. Each entry is one comparison, and each level has about n entries. The number of levels is about log2(n), which is the number of times you can halve n before reaching 1. So the build does about n * log2(n) comparisons.

Here is the number of levels for some sizes. log2(n) is the power that 2 must be raised to in order to get n, so log2(8) is 3, and log2(100) is about 6.6.

• For n = 6, the levels are 0, 1 and 2, so there are 3 levels.
• For n = 8, the levels are 0, 1, 2 and 3, so there are 4 levels.
• For n = 100000, the levels are 0 through 16, so there are 17 levels.

Answering a query in constant time

Now the query. Given l and r, the length of the range is length = r - l + 1. Find the largest exponent k where 2^k is at most length. Call this floor(log2(length)). The word "floor" means we round down. For the range from 0 to 4 in the example, the length is 5. The powers of two up to 5 are 1, 2 and 4, so k is 2 and 2^k is 4.

Now take two blocks of length 2^k that cover the range. One block starts at l. The other block ends at r, so it starts at r - 2^k + 1. Because 2^k is more than half of length, the two blocks together cover every position from l to r. They may overlap, and the overlap is fine. The answer is the smaller of the two stored minimums.

Here is the query (0, 4) in the example. The length is 5, k is 2, and 2^k is 4. The first block starts at position 0 and covers 5, 2, 8, 6. Its stored value is sp[2][0], which is 2. The second block starts at position 4 - 4 + 1 = 1 and covers 2, 8, 6, 1. Its stored value is sp[2][1], which is 1. The answer is min(2, 1), which is 1.

Why does overlap not spoil the answer? The minimum has a property that the sum does not have. Taking the minimum of a value with itself gives the same value, so min(x, x) is x. An item that appears in both blocks is counted twice, but counting it twice does not change the smallest value. A sum would be wrong in this case, because adding the overlapping items twice gives a different total. That is why sparse tables work for minimum and maximum but not for sum. Operations with this property are called idempotent, which is a word that means "doing it again changes nothing".

The query uses only a few steps: compute the length, find k, read two table entries, and compare them. None of those steps grows with the size of the range. That is the reason the query is called constant time.

Finding k without a loop

The number k can be found with a loop that doubles a counter, but Python has a shorter way. The method int.bit_length() returns how many binary digits a number needs. The number 7 is written in binary as 111, which has 3 digits, so (7).bit_length() is 3. Subtracting 1 gives 2, which is floor(log2(7)).

def floor_log2(x):
    return x.bit_length() - 1

The method is correct for every positive whole number, and the programs below test it through the queries. The method works on whole numbers only, so it never runs into the rounding that a division of logarithms can cause.

A complete program

The program below builds the table for the example list, prints each level, runs four queries, and then checks 40,000 random queries against the plain loop. The random check is the way to be sure the table is right. A few hand examples can miss a mistake, but many random checks against a simple, obviously correct method catch most of them.

The output is:

levels = 3
k=0: 5 2 8 6 1 7
k=1: 2 2 6 1 1
k=2: 2 1 1
min[0..5] = 1
min[1..2] = 2
min[2..4] = 1
min[3..3] = 6
random queries checked = 40000 all match

Look at the level lines. Level k=1 has five entries, not six, because a block of length 2 cannot start at the last position. The range range(n - (1 << k) + 1) in build_sparse stops the row at the right size. The line min[3..3] = 6 shows a query of length 1. Its k is 0, so both table reads are sp[0][3], which is the item itself.

The random check uses random.Random(42), a seeded generator, so the same numbers appear every time you run it.

A second example with a harder shape

The first example had an answer that sat at one end. The next example is harder because the smallest value sits in the overlap of the two blocks. Take the list [9, 4, 7, 3, 8, 6, 5], which has 7 items. Its levels are 0, 1 and 2, because floor(log2(7)) is 2.

Build the table by hand. Level 1 takes neighbours: 9 and 4 give 4, 4 and 7 give 4, 7 and 3 give 3, 3 and 8 give 3, 8 and 6 give 6, and 6 and 5 give 5. So level 1 is 4 4 3 3 6 5. Level 2 takes blocks of four: starting at 0 the block is 9, 4, 7, 3, which gives 3. Starting at 1 the block is 4, 7, 3, 8, which gives 3. Starting at 2 the block is 7, 3, 8, 6, which gives 3. Starting at 3 the block is 3, 8, 6, 5, which gives 3. So level 2 is 3 3 3 3.

Now the query (1, 5). The range from position 1 to position 5 holds 4, 7, 3, 8 and 6. Its length is 5 and k is 2. The first block starts at position 1 and covers 4, 7, 3, 8, with stored value 3. The second block starts at position 5 - 4 + 1 = 2 and covers 7, 3, 8, 6, with stored value 3. The answer is 3. The value 3 is in both blocks, and the overlap is what lets the two blocks cover the whole range with no gap.

Running build_sparse on this list gives level 1 as 4 4 3 3 6 5 and level 2 as 3 3 3 3, which matches the hand work. The plain loop also gives 3 for the same query, so the two methods agree. The point of the example is that you did not need to scan the middle items to get the answer. You read two stored values, and one of them already held the 3.

Limits and costs

The sparse table has three limits you must know before you use it.

The first limit is that the list must not change. If you set a[4] from 1 to 9 in the example, the table still holds the old value, and query_min(sp, 0, 5) still returns 1, even though the true minimum is now 2. A change to one item may affect many table entries, because each block that contains that item stores an old answer. Rebuilding the whole table costs about n * log2(n) comparisons again. If values change often, a segment tree is the better tool. It handles a change to one value in about log2(n) steps, and a later lesson in this module covers changes to whole ranges.

The second limit is memory. The table stores levels lists of entries. For 100,000 numbers, the table has 17 levels and about 1.57 million entries in total. Each list slot holds a reference, and the lists alone take about 12.8 megabytes on the machine used to check this lesson. Each int object adds more, so the real use is higher. That is usually fine on a laptop, but it grows with n * log2(n), not with n alone.

The third limit is the operation. The table works for minimum, maximum, and any other operation that is idempotent, which means applying it to the same value twice gives that value again. It does not work for sum, because overlapping blocks would count some items twice. Greatest common divisor is also idempotent, because gcd(x, x) is x, so a sparse table answers gcd queries too. The next lesson covers gcd in a segment tree, where the tree stores one answer per node and does not need the overlap at all.

Common mistakes

Using the wrong right index. The second block must end at r, so it starts at r - 2^k + 1. A common error is to leave out the + 1 or to subtract only 2^k. Here is the query (0, 4) on the example list, first with the correct index and then with the wrong one. The correct answer is 1, but the wrong index gives 2 because it skips the position with the value 1.

l, r = 0, 4
k = floor_log2(r - l + 1)
right = min(sp[k][l], sp[k][r - (1 << k) + 1])  # correct: 1
wrong = min(sp[k][l], sp[k][r - (1 << k)])      # wrong: 2

This bug does not crash. It prints a plausible number that is simply too large. This is the reason the random check against the plain loop matters.

Asking for an index past the end of the list. A query must satisfy 0 <= l <= r < n. If r is too big, the table read goes past the end. Here is a small program that reads past the end of a two-item list, and the message Python prints for it:

sp = [3, 1]
r = 2
print(sp[r])

Traceback (most recent call last):
  File "oob.py", line 3, in <module>
    print(sp[r])
          ~~^^^
IndexError: list index out of range

The last line names the error. The line above it shows the code that failed, and the small marks under sp[r] point at the index. The File line shows the full path to your file, so it will differ on your computer. Read the line, then check the values of l and r that were passed in. In a sparse table, a bad r is the usual cause.

Building too few levels. If the number of levels is computed as log2(n) without the + 1, the table is missing the top level. A query with a long range then reads a row that was never created, and the same error appears with a different index. The fix is the line levels = floor_log2(n) + 1, which gives one level for each power of two that fits.

Expecting updates to show up in the table. As described in the limits, a changed list item does not update the table. The table keeps the answer from the time it was built. Rebuild the table after changes, or switch to a structure that supports updates.

Dividing logarithms to find k. Some people write math.log(length, 2) and round the result. This uses floating-point numbers, which round, so the result can be off for some lengths. The bit_length method uses whole numbers only, so use it.

Practice

1. Build level 1 of the sparse table for the list [3, 9, 4, 4, 0]. Write the four values.

Show the answer

Level 1 holds the minimum of each pair of neighbours: min(3, 9) is 3, min(9, 4) is 4, min(4, 4) is 4, and min(4, 0) is 0. The level is 3 4 4 0.

2. Using the list and table from Exercise 1, answer the query (1, 3) with the sparse table method. Then check it with the plain loop.

Show the answer

The length is 3, so k is 1 and 2^k is 2. The first block starts at 1 and holds sp[1][1], which is 4. The second block starts at 3 - 2 + 1 = 2 and holds sp[1][2], which is 4. The answer is 4. The plain loop looks at 9, 4 and 4 and gets 4 as well.

3. How many levels does a sparse table need for a list of 8 items? List the block length of each level.

Show the answer

floor(log2(8)) is 3, so there are 3 + 1 levels, which is 4. The block lengths are 1, 2, 4 and 8. The top level has one block that covers the whole list.

4. A query (0, 6) on a list of 7 items has length 7. Which k does it use, and which two blocks cover the range?

Show the answer

floor(log2(7)) is 2, so k is 2 and each block has length 4. The first block starts at 0 and covers positions 0 to 3. The second block starts at 6 - 4 + 1 = 3 and covers positions 3 to 6. Together they cover all seven positions, and position 3 is in both blocks.

5. Change the program so that it answers the range maximum instead of the minimum. Name every line you change.

Show the answer

Replace min with max in build_sparse, in query_min and in brute_min. Rename the functions if you want, for example to query_max. The rest of the code is the same, because the maximum is also idempotent, so the overlap still does no harm.

Summary

• A sparse table stores the minimum of every block whose length is a power of two, one row per length.
• Each row is built from the row before it, using min of two neighbouring blocks.
• A query takes the largest power of two that fits its length and reads two overlapping blocks.
• The overlap is safe for minimum because min(x, x) equals x, and it would be wrong for sum.
• The table is fixed: a change to the list needs a rebuild, and that is why segment trees exist for changing values.