Why this matters
A range-minimum query asks for the smallest value between two positions of an array. For example, a game might store the price of a stock each day and ask for the lowest price between day 10 and day 40. The question comes up often in programs that answer many queries against one array that does not change.
The simplest method is a loop from the left end to the right end. That takes time proportional to the length of the range. If there are a million queries on a million-value array, the loops can take on the order of a trillion steps. This lesson builds a structure that answers each query in a fixed small number of steps, after one preparation pass. The structure is called a sparse table. "Sparse" here does not mean empty. It means the table stores only some of the possible ranges, namely the ranges whose lengths are powers of two.
The table works only when the array never changes. If you change a value, the table keeps the old answers. Later lessons in this module handle arrays that change. This lesson has one job: fixed array, many minimum queries, fast answers.
The plain loop, and what it costs
Start with a small array. Index 0 is the first value. Indexes count from 0 in C++, so a[0] is the first element.
const std::vector<int> a = {5, 2, 8, 6, 3, 6, 1, 4};To find the minimum of positions 2 through 5, you look at the values 8, 6, 3 and 6, and keep the smallest. The answer is 3. The loop code is short:
int smallest = a[2];
for (std::size_t i = 3; i <= 5; ++i) {
smallest = std::min(smallest, a[i]);
}Each query takes as many steps as there are positions in the range. With q queries on an array of length n, the total work can reach q * n steps in the worst case. That is fine for ten queries. It is slow for a million queries on a million values.
The idea: blocks whose length is a power of two
Think of the array as a row of boxes. Each box holds one value. Now group the boxes into blocks. A block of length 1 is one box. A block of length 2 covers two boxes side by side. A block of length 4 covers four boxes. The lengths 1, 2, 4, 8 and so on are the powers of two. Each power of two is a level. Level 0 has blocks of length 1, level 1 has blocks of length 2, level 2 has blocks of length 4, and level k has blocks of length 2 to the power k.
The table stores one number for each block. For level k and start position i, the entry table[k][i] holds the smallest value in the block that starts at position i and has length 2^k. The name table[k][i] is a plain two-index lookup: first pick the level, then the start position.
For the array above, the table has four levels, because the longest block that fits is 8 positions long. Here is the table. Each row is one level. The row for level k has one entry for each block of that length that fits inside the array, so the rows get shorter as the blocks get longer.
level 0 (blocks of 1): 5 2 8 6 3 6 1 4
level 1 (blocks of 2): 2 2 6 3 3 1 1
level 2 (blocks of 4): 2 2 3 1 1
level 3 (blocks of 8): 1Check one entry by hand. Level 1, start position 2, covers positions 2 and 3, which hold 8 and 6. The smaller value is 6, and that is the third entry of the level 1 row. Level 2, start position 1, covers positions 1 through 4, which hold 2, 8, 6 and 3. The smallest is 2, and that is the second entry of the level 2 row.
The table is built from the level below. A block of length 2^k is two blocks of length 2^(k-1) placed one after the other. So its minimum is the smaller of two lower-level entries:
table[k][i] = min(table[k-1][i], table[k-1][i + 2^(k-1)])
Look at level 2, start 0. It is the smaller of level 1 start 0 (the value 2) and level 1 start 2 (the value 6). That gives 2, which matches the table. Each level costs one pass over the array, and there are about log2(n) levels, so the build takes time proportional to n times the number of levels.
Answering a query with two blocks
Now take a query for positions l through r, both included. Let len be the number of positions, so len = r - l + 1. Find the largest power of two that is at most len. Call its exponent k, so 2^k <= len < 2^(k+1).
Two blocks of length 2^k will cover the query. The first block starts at l. The second block ends at r, so it starts at r - 2^k + 1. Both blocks fit inside [l, r]. Together they cover every position in the range, because the first block reaches from l up to l + 2^k - 1, and the second block reaches from r - 2^k + 1 up to r. The two blocks may overlap in the middle. That is fine. The answer is the smaller of the two stored minimums.
Here is a query for positions 0 through 6 on the array above. The length is 7. The largest power of two at most 7 is 4, so k is 2. The first block starts at 0 and covers positions 0 through 3. Its stored value, table[2][0], is 2. The second block ends at 6, so it starts at 6 - 4 + 1 = 3. It covers positions 3 through 6, and its stored value, table[2][3], is 1. The answer is min(2, 1) = 1. The actual values from position 0 to 6 are 5, 2, 8, 6, 3, 6 and 1, and the smallest is 1. The answer is right.
Here is a query for positions 2 through 5. The length is 4, so k is 2. The two blocks both start at 2, because r - 2^k + 1 equals 5 - 4 + 1 = 2. The answer is just table[2][2], which is 3. Both blocks being the same is allowed.
Overlap does not break the answer, because taking a minimum is forgiving. If a value is counted twice, the minimum does not change. The minimum of 4, 4 and 9 is 4, the same as the minimum of 4 and 9. Sums do not behave this way, because counting a value twice adds it twice. This is the main reason the sparse table uses min and not sum.
The work per query is fixed. You compute the length, find k in one step, and read two numbers from the table. The time does not depend on how long the range is. That is what is meant by constant time, or O(1), in this lesson.
Finding k quickly
The exponent k is the position of the highest set bit of len, which is the leftmost 1 when len is written in binary. In C++20 the standard library gives you this with std::bit_width. For a positive number len, std::bit_width(len) returns the number of bits needed to write len in binary. For len = 7, the binary form is 111, which has 3 bits, so std::bit_width(7) is 3. Subtract 1 to get k = 2. For len = 8, the binary form is 1000, which has 4 bits, so k = 3. The subtraction matches the definition: 2^3 = 8 is the largest power of two at most 8.
The library function takes an unsigned type. The lesson's code uses std::size_t, which is unsigned.
Program 1: build the table and answer queries
The first program builds the table for the array from the examples and answers three queries. The class stores the table as a vector of vectors. Level k is table_[k], and it has one entry per block that fits. The build loop uses len for the block length, starting at 2 and doubling each time.
#include <algorithm>
#include <bit>
#include <cstddef>
#include <iostream>
#include <vector>
// table_[k][i] holds the minimum of the 2^k values starting at index i.
class SparseMin {
public:
explicit SparseMin(const std::vector<int>& values) {
const std::size_t n = values.size();
table_.push_back(values); // level 0: blocks of length 1
for (std::size_t len = 2; len <= n; len *= 2) {
const std::vector<int>& prev = table_.back();
const std::size_t half = len / 2;
std::vector<int> level(n - len + 1);
for (std::size_t i = 0; i + len <= n; ++i) {
level[i] = std::min(prev[i], prev[i + half]);
}
table_.push_back(std::move(level));
}
}
// Minimum of values[l..r], both ends included. Requires l <= r < n.
int query(std::size_t l, std::size_t r) const {
const std::size_t len = r - l + 1;
const std::size_t k = std::bit_width(len) - 1; // largest k with 2^k <= len
return std::min(table_[k][l], table_[k][r + 1 - (std::size_t{1} << k)]);
}
private:
std::vector<std::vector<int>> table_;
};
int main() {
const std::vector<int> a = {5, 2, 8, 6, 3, 6, 1, 4};
const SparseMin sp(a);
std::cout << "min of [0..3] = " << sp.query(0, 3) << '\n';
std::cout << "min of [2..5] = " << sp.query(2, 5) << '\n';
std::cout << "min of [4..7] = " << sp.query(4, 7) << '\n';
std::cout << "min of [0..7] = " << sp.query(0, 7) << '\n';
return 0;
}Compile and run it. The flags -std=c++20 select the C++20 language version, -Wall and -Wextra turn on the common warnings, and -o names the output file.
g++ -std=c++20 -Wall -Wextra -o sparse1 sparse1.cpp && ./sparse1The output is:
min of [0..3] = 2
min of [2..5] = 3
min of [4..7] = 1
min of [0..7] = 1Check each line against the array 5 2 8 6 3 6 1 4. Positions 0 to 3 hold 5, 2, 8 and 6, and the smallest is 2. Positions 2 to 5 hold 8, 6, 3 and 6, and the smallest is 3. Positions 4 to 7 hold 3, 6, 1 and 4, and the smallest is 1. The whole array has minimum 1.
Printing the table
The second program prints every level, so you can compare the table with the hand-built version above. It also shows the stale-table problem, which the mistakes section returns to.
#include <algorithm>
#include <bit>
#include <cstddef>
#include <iostream>
#include <vector>
class SparseMin {
public:
explicit SparseMin(const std::vector<int>& values) {
const std::size_t n = values.size();
table_.push_back(values);
for (std::size_t len = 2; len <= n; len *= 2) {
const std::vector<int>& prev = table_.back();
const std::size_t half = len / 2;
std::vector<int> level(n - len + 1);
for (std::size_t i = 0; i + len <= n; ++i) {
level[i] = std::min(prev[i], prev[i + half]);
}
table_.push_back(std::move(level));
}
}
int query(std::size_t l, std::size_t r) const {
const std::size_t len = r - l + 1;
const std::size_t k = std::bit_width(len) - 1;
return std::min(table_[k][l], table_[k][r + 1 - (std::size_t{1} << k)]);
}
void print() const {
for (std::size_t k = 0; k < table_.size(); ++k) {
std::cout << "level " << k << " (blocks of " << (std::size_t{1} << k) << "):";
for (int v : table_[k]) std::cout << ' ' << v;
std::cout << '\n';
}
}
private:
std::vector<std::vector<int>> table_;
};
int main() {
const std::vector<int> a = {5, 2, 8, 6, 3, 6, 1, 4};
SparseMin sp(a);
sp.print();
std::cout << "query [0, 2] = " << sp.query(0, 2) << '\n';
std::cout << "query [2, 5] = " << sp.query(2, 5) << '\n';
std::cout << "query [0, 6] = " << sp.query(0, 6) << '\n';
// The table is a copy of the values at build time. Change one value and it is stale.
std::vector<int> b = a;
b[1] = 9;
std::cout << "after b[1] = 9, the true min of [0, 2] = "
<< *std::min_element(b.begin(), b.begin() + 3) << '\n';
std::cout << "the table still says = " << sp.query(0, 2) << '\n';
return 0;
}The output is:
level 0 (blocks of 1): 5 2 8 6 3 6 1 4
level 1 (blocks of 2): 2 2 6 3 3 1 1
level 2 (blocks of 4): 2 2 3 1 1
level 3 (blocks of 8): 1
query [0, 2] = 2
query [2, 5] = 3
query [0, 6] = 1
after b[1] = 9, the true min of [0, 2] = 5
the table still says = 2The printed levels match the hand-built table. Level 3 has one entry, because only one block of length 8 fits in an array of length 8. The last two lines show the limit of this structure: after the value at position 1 changed from 2 to 9, the true minimum of positions 0 to 2 is 5, but the table still answers 2.
Program 2: check the table against a plain loop
Hand examples can miss mistakes. A better test compares the table with the slow loop on many random arrays and all possible ranges. The program below uses a fixed random seed, so the same numbers come out on every run. It builds 200 random arrays of length 1 to 40, then checks every range of each array.
#include <algorithm>
#include <bit>
#include <cstddef>
#include <iostream>
#include <random>
#include <vector>
class SparseMin {
public:
explicit SparseMin(const std::vector<int>& values) {
const std::size_t n = values.size();
table_.push_back(values);
for (std::size_t len = 2; len <= n; len *= 2) {
const std::vector<int>& prev = table_.back();
const std::size_t half = len / 2;
std::vector<int> level(n - len + 1);
for (std::size_t i = 0; i + len <= n; ++i) {
level[i] = std::min(prev[i], prev[i + half]);
}
table_.push_back(std::move(level));
}
}
int query(std::size_t l, std::size_t r) const {
const std::size_t len = r - l + 1;
const std::size_t k = std::bit_width(len) - 1;
return std::min(table_[k][l], table_[k][r + 1 - (std::size_t{1} << k)]);
}
std::size_t levels() const { return table_.size(); }
private:
std::vector<std::vector<int>> table_;
};
int brute_min(const std::vector<int>& a, std::size_t l, std::size_t r) {
return *std::min_element(a.begin() + static_cast<std::ptrdiff_t>(l),
a.begin() + static_cast<std::ptrdiff_t>(r) + 1);
}
int main() {
std::mt19937 rng(12345); // fixed seed, so the run is the same every time
std::uniform_int_distribution<int> value(-50, 50);
int checked = 0;
int mismatches = 0;
for (int trial = 0; trial < 200; ++trial) {
const std::size_t n = 1 + rng() % 40;
std::vector<int> a(n);
for (int& x : a) x = value(rng);
const SparseMin sp(a);
for (std::size_t l = 0; l < n; ++l) {
for (std::size_t r = l; r < n; ++r) {
++checked;
if (sp.query(l, r) != brute_min(a, l, r)) ++mismatches;
}
}
}
std::cout << "queries checked: " << checked << '\n';
std::cout << "mismatches: " << mismatches << '\n';
const std::vector<int> small = {4, 1, 7, 1, 9};
std::cout << "levels for n = 5: " << SparseMin(small).levels() << '\n';
return 0;
}The output on the machine used to write this lesson, with g++ 15.2.0, is:
queries checked: 60301
mismatches: 0
levels for n = 5: 3The count 60301 is the number of pairs (l, r) with l <= r, summed over all 200 arrays. Zero mismatches means every checked answer matched the plain loop. The last line shows the level count for an array of length 5. Levels with block lengths 1, 2 and 4 fit. A block of length 8 does not, so there are 3 levels.
Program 3: return the position of the minimum
Many questions ask where the minimum is, not only what it is. For example, a shop wants the day with the lowest price, not only the price. The table can store indexes instead of values. Each entry then holds the position of the smallest value in its block. When two blocks are compared, the code looks up the values at the two stored positions.
Ties need a rule. If two positions hold the same minimum value, the code returns the smaller position. The rule makes the answer predictable, so the same query always gives the same position.
#include <algorithm>
#include <bit>
#include <cstddef>
#include <iostream>
#include <numeric>
#include <vector>
// The table stores positions. Values are looked up through values_.
class SparseArgMin {
public:
explicit SparseArgMin(const std::vector<int>& values) : values_(values) {
const std::size_t n = values.size();
std::vector<std::size_t> level0(n);
std::iota(level0.begin(), level0.end(), std::size_t{0});
table_.push_back(std::move(level0));
for (std::size_t len = 2; len <= n; len *= 2) {
const std::vector<std::size_t>& prev = table_.back();
const std::size_t half = len / 2;
std::vector<std::size_t> level(n - len + 1);
for (std::size_t i = 0; i + len <= n; ++i) {
level[i] = better(prev[i], prev[i + half]);
}
table_.push_back(std::move(level));
}
}
// Position of the smallest value in [l..r]. On a tie, the smaller position wins.
std::size_t query(std::size_t l, std::size_t r) const {
const std::size_t len = r - l + 1;
const std::size_t k = std::bit_width(len) - 1;
return better(table_[k][l], table_[k][r + 1 - (std::size_t{1} << k)]);
}
private:
// Returns whichever position holds the smaller value. Ties go to the smaller position.
std::size_t better(std::size_t i, std::size_t j) const {
if (values_[i] != values_[j]) return values_[i] < values_[j] ? i : j;
return std::min(i, j);
}
std::vector<int> values_;
std::vector<std::vector<std::size_t>> table_;
};
int main() {
const std::vector<int> prices = {4, 1, 7, 1, 9};
const SparseArgMin sp(prices);
std::cout << "lowest price in days [0..4] is on day " << sp.query(0, 4) << '\n';
std::cout << "lowest price in days [2..4] is on day " << sp.query(2, 4) << '\n';
std::cout << "lowest price in days [1..3] is on day " << sp.query(1, 3) << '\n';
return 0;
}The output is:
lowest price in days [0..4] is on day 1
lowest price in days [2..4] is on day 3
lowest price in days [1..3] is on day 1The array has two days with price 1, on days 1 and 3. The first query covers both, and the tie rule returns day 1. The third query covers both as well, and it also returns day 1. The second query covers only day 3, so the answer is day 3.
The class keeps a copy of the values. The table itself holds positions, and each comparison reads two values. The build and query times are the same as before. The extra memory is the copy of the values, which is one more array of length n.
Common mistakes
Passing a signed number to std::bit_width
std::bit_width only accepts unsigned integers. A common mistake is to pass an int for the length, because loops often use int. The compiler stops with an error. Compiling this code with g++ 15.2.0 gives:
mistake1.cpp:7:32: error: no matching function for call to ‘bit_width(int&)’
/usr/include/c++/15/bit:397:62: note: the expression ‘std::__is_unsigned_integer<_Tp>::value [with _Tp = int]’ evaluated to ‘false’The fix is to use std::size_t for the length, as the lesson's code does. If a value must start as an int, convert it once with static_cast<std::size_t>(len) before the call.
Building one level too few
The build loop must keep going while the block length fits inside the array. If the loop stops early, the table lacks the level that a long query needs. The query still computes a valid k, but the lookup goes past the last level that exists. This version has a bug: the loop condition is len < n / 2 instead of len <= n. For an array of length 8, it stops before building the block length 4 level, and a query of length 7 needs that level.
Compiling with -D_GLIBCXX_ASSERTIONS turns on checks in the standard library, so an out-of-range lookup stops the program with a message. Running the buggy version prints this:
/usr/include/c++/15/bits/stl_vector.h:1282: constexpr std::vector<_Tp, _Alloc>::const_reference std::vector<_Tp, _Alloc>::operator[](size_type) const [with _Tp = std::vector<int>; _Alloc = std::allocator<std::vector<int> >; const_reference = const std::vector<int>&; size_type = long unsigned int]: Assertion '__n < this->size()' failed.The exit code is 134, which means the program was stopped by an abort signal. The line number and wording of the message change between library versions. The message names the failed index check on the outer vector, which holds the levels. The fix is the loop condition len <= n, as written in the lesson. Without the checks flag, the same bug may not stop the program. It may read a wrong number and print a wrong answer, so the flag is useful while testing.
Using the table after the array changes
A sparse table is built once. If you change a value in the array and do not rebuild, the table still holds the old minimums. Program 2 shows this: after the value at position 1 changed from 2 to 9, the table kept answering 2, and the true answer is 5. No error is printed. The program simply gives a wrong answer. The fix is either to rebuild the whole table after each change, which is slow if the array changes often, or to use a different structure that supports updates. The later lessons in this module cover updates.
Confusing block length with block count
The level k table has blocks of length 2^k. The number of entries in that level is n - 2^k + 1, not n / 2^k. The entries overlap. Block starts at positions 0 and 1 both exist at level 1 for an array of length 8, and they share position 1. Writing n / 2^k gives too few entries, and the last valid query can read past the end of the row.
Using a sum instead of a minimum
The overlap in the two-block query is safe only for operations where repeating a value does not change the result, such as minimum and maximum. Using the same code with addition gives wrong answers, because the overlapping part is counted twice. A sum needs a different method, such as prefix sums. Keep this rule in mind before you reuse the table for another operation: the operation must give the same result when a value is included twice.
Practice
Exercise 1
Build the sparse table by hand for the array 3 1 4 1 5. Write each level on one line, the way the lesson did.
Show the answer
Level 0 is the array itself: 3 1 4 1 5. Level 1 has blocks of length 2, and it has 5 - 2 + 1 = 4 entries. They are min(3,1) = 1, min(1,4) = 1, min(4,1) = 1 and min(1,5) = 1, so the row is 1 1 1 1. Level 2 has blocks of length 4, and it has 5 - 4 + 1 = 2 entries. They are min(3,1,4,1) = 1 and min(1,4,1,5) = 1, so the row is 1 1. The table has three levels. Level 3 would need blocks of length 8, which do not fit in 5 positions.
Exercise 2
For an array of length 8, which two blocks answer the query for positions 1 through 6? Give the start position and the level of each block.
Show the answer
The length is 6 - 1 + 1 = 6. The largest power of two at most 6 is 4, so k is 2 and each block has length 4. The first block starts at l = 1 and covers positions 1 to 4. The second block ends at r = 6, so it starts at 6 - 4 + 1 = 3 and covers positions 3 to 6. Both blocks are on level 2. The two blocks overlap at positions 3 and 4, which is allowed for a minimum.
Exercise 3
Why does the sparse table answer a sum query incorrectly if the two blocks are combined in the same way? Give a small example with numbers.
Show the answer
Take the array 2 3 4 and the query for positions 0 to 2. The length is 3. The largest power of two is 2, so k is 1. The first block covers positions 0 and 1, with sum 5. The second block covers positions 1 and 2, with sum 7. Adding the two stored sums gives 12, but the true sum of positions 0 to 2 is 9. Position 1, with value 3, was counted twice. A minimum does not change when a value is counted twice, so the same overlap is harmless for min.
Exercise 4
How many levels does a sparse table have for an array of length 16? How many entries does the level with blocks of length 4 have?
Show the answer
The block lengths that fit are 1, 2, 4, 8 and 16. Those are the powers of two from 2^0 to 2^4, so there are 5 levels. The level with blocks of length 4 has 16 - 4 + 1 = 13 entries. Its starts run from position 0 to position 12.
Exercise 5
Change the code in Program 1 so that it returns the maximum of a range instead of the minimum. Name the lines that change.
Show the answer
Two lines change. In the constructor, std::min(prev[i], prev[i + half]) becomes std::max(prev[i], prev[i + half]). In query, std::min(table_[k][l], ...) becomes std::max(table_[k][l], ...). Nothing else changes, because the maximum also gives the same result when a value is counted twice. The table layout, the level sizes and the value of k stay the same.
Summary
- A sparse table stores the minimum of every block whose length is a power of two, one table row per length.
- Level
khas blocks of length2^k, and each entry is the smaller of two entries from levelk - 1. - A query finds
kfrom the query length, then takes the smaller of two overlapping blocks of length2^k. - Each query is constant time after a build that takes about
ntimes log2(n) steps, but the table does not handle changes to the array. - Overlap is safe for minimum and maximum because repeating a value does not change them, and it is not safe for sums.
- Store positions instead of values when the question asks where the minimum is, and break ties by taking the smaller position.