Sparse table

A sparse table answers a range-minimum query, "what is the smallest element between positions l and r?", in constant time, for an array that doesn't change. Building it takes O(n \log n) time and memory, and the same works for the maximum. If the array changes between queries, use a segment tree instead.

Scanning the range finds its minimum, but one scan takes up to $n$ steps (time complexity), which is too slow when a long array gets many queries. A sparse table stores in advance the minima of O(n \log n) ranges whose lengths are powers of two, and any range is covered by two of them.

How it works

A block is a range of the array whose length is a power of two: 1, 2, 4, 8, and so on. The table has one cell for every block, holding its minimum. Blocks of one length form a level: level $k$ has the blocks of 2^k elements, one for each starting position i. Level 0, with blocks of length 1, is the array itself.

Here is level 1 for the array 6, 3, 8, 5, 9, 4, 7, 2 at positions 1 to 8.

Fig. 1. Each cell of level 1 holds the smaller of the two elements that start at its position.

Each level comes from the one above it. A block of 4 is two blocks of 2 side by side, so its cell on level 2 is the smaller of two cells of level 1: the one at i and the one at i + 2. A block of 8 is two blocks of 4, from i and from i + 4. Each cell costs one comparison. With $n$ elements there are \log_2 n + 1 levels (\log_2 n here means the largest $k$ with 2^k \le n), each with at most $n$ cells, so the build takes O(n \log n).

Here is the whole build, one cell at a time.

The green cell is the new one, and the outlined cells are the two it comes from. Cell 1 of level 1 covers positions 1 to 2: the smaller of cells 1 and 2 of level 0, 6 and 3, is 3.

Cell 2 of level 1 covers positions 2 to 3: the smaller of cells 2 and 3 of level 0, 3 and 8, is 3.

Cell 3 of level 1 covers positions 3 to 4: the smaller of cells 3 and 4 of level 0, 8 and 5, is 5.

Cell 4 of level 1 covers positions 4 to 5: the smaller of cells 4 and 5 of level 0, 5 and 9, is 5.

Cell 5 of level 1 covers positions 5 to 6: the smaller of cells 5 and 6 of level 0, 9 and 4, is 4.

Cell 6 of level 1 covers positions 6 to 7: the smaller of cells 6 and 7 of level 0, 4 and 7, is 4.

Cell 7 of level 1 covers positions 7 to 8: the smaller of cells 7 and 8 of level 0, 7 and 2, is 2.

Cell 1 of level 2 covers positions 1 to 4: the smaller of cells 1 and 3 of level 1, 3 and 5, is 3.

Cell 2 of level 2 covers positions 2 to 5: the smaller of cells 2 and 4 of level 1, 3 and 5, is 3.

Cell 3 of level 2 covers positions 3 to 6: the smaller of cells 3 and 5 of level 1, 5 and 4, is 4.

Cell 4 of level 2 covers positions 4 to 7: the smaller of cells 4 and 6 of level 1, 5 and 4, is 4.

Cell 5 of level 2 covers positions 5 to 8: the smaller of cells 5 and 7 of level 1, 4 and 2, is 2.

Cell 1 of level 3 covers positions 1 to 8: the smaller of cells 1 and 5 of level 2, 3 and 2, is 2.

1/13

Fig. 2. Step through the build with the buttons or the arrow keys. Each new cell is the smaller of the two outlined cells.

A query whose length is a power of two is one cell, but positions 2 to 8 are 7 elements, and no level has blocks of 7. Cutting the range into blocks of 4, 2 and 1 works, but a long range can need up to \log_2 n + 1 blocks.

Instead, take the largest power of two that fits in 7, which is 4, and use two blocks of that length: the red block starts at position 2 (positions 2 to 5) and the blue block ends at position 8 (positions 5 to 8).

Fig. 3. The red block covers positions 2 to 5, the blue block 5 to 8. The answer is under the range.

The red block gives 3, the blue block gives 2, and the smaller of them, 2, is the right answer, even though the 9 at position 5 is in both. Both blocks lie inside the range, because neither is longer than it. They also leave no gap: with 2^k the largest power of two that fits, 2 \cdot 2^k is more than the length (8 > 7 here), so the two blocks together are longer than the range and must overlap. So any query reads two cells: $O(1)$.

The overlap is safe only because counting an element twice doesn't change the result. That holds for the minimum, the maximum, the gcd, and bitwise AND and OR. It fails for the sum: the red block sums to 25 and the blue to 22, which gives 47, but positions 2 to 8 sum to 38.

Two more queries: one whose blocks share one element, and one of length 1.

Query 4 to 6: 3 elements, so blocks of 2. On the row k = 0 the red block is positions 4 to 5, the blue block 5 to 6, and position 5, in both, is shaded darker. The outlined cells 4 and 5 of level 1 hold 5 and 4, so the answer is 4.

Query 5 to 5: one element, so blocks of 1. The red and the blue block are both position 5, so the query reads cell 5 of level 0 twice, and the answer is 9.

1/2

Fig. 4. Step through the two queries with the buttons or the arrow keys.

In C++

The table is a vector of vectors st, with positions from 1 as in the arrays article: st[k][i] is the minimum of the 1 << k elements from position i (1 << k is 2^k, a shift). Level k is built from level k - 1: st[k][i] is the smaller of st[k - 1][i] and st[k - 1][i + (1 << (k - 1))].

A query from l to r first picks the level: the largest k with 1 << k not larger than r - l + 1. An array lg gives it at once: lg[1] = 0, and lg[x] = lg[x / 2] + 1, since halving x lowers that k by one. The table needs lg[n] + 1 levels, from 0 to lg[n]. The query then takes two blocks of 1 << k elements, one from l and one ending at r.

The input is n (1 \le n \le 10^5), then n numbers, then q, then q lines l r, where l may be larger than r. The program prints the minimum of positions l to r for each line. The example above is this input:

8
6 3 8 5 9 4 7 2
3
2 8
4 6
5 5

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int main() {
    int n;
    cin >> n;

    // lg[x]: largest k with 2^k <= x
    vector<int> lg(n + 1, 0);
    for (int x = 2; x <= n; x++) lg[x] = lg[x / 2] + 1;

    int levels = lg[n] + 1;
    vector<vector<int>> st(levels, vector<int>(n + 1));

    // level 0 is the array
    for (int i = 1; i <= n; i++) cin >> st[0][i];

    // each level from two cells of the level above
    for (int k = 1; k < levels; k++)
        for (int i = 1; i + (1 << k) - 1 <= n; i++)
            st[k][i] = min(st[k - 1][i], st[k - 1][i + (1 << (k - 1))]);

    int q;
    cin >> q;
    for (int j = 0; j < q; j++) {
        int l, r;
        cin >> l >> r;
        if (l > r) swap(l, r);   // remove if the input guarantees l <= r

        // pick the level
        int k = lg[r - l + 1];

        // take two blocks: from l, and ending at r
        cout << min(st[k][l], st[k][r - (1 << k) + 1]) << '\n';
    }
}

Maximum and the position of the minimum

For the maximum, change both min calls to max. When the query asks where the minimum is, store positions instead of values: level 0 holds i itself, and each cell keeps whichever of its two positions has the smaller element a[p]. The query compares the two positions it gets the same way. Keep the array a next to the table for these comparisons.

Examples of use

The same table answers the gcd of a range with gcd in place of min (practice problem 10491).

Binary search over range minima

Some problems ask how far right a range from i can go while its minimum stays above some x. As r grows, the minimum of i to r can only fall, so binary search on r works, with an $O(1)$ query at each step: O(\log n) in total. Practice problem 1102 uses this together with the position of the maximum.

Lowest common ancestor

Write down the vertices of a tree as a DFS walks it, writing a vertex again each time the DFS comes back to it from a child: between the entries of u and v, the vertex closest to the root is their lowest common ancestor. That is a range minimum over the depths on a fixed array, found with the position variant above, and the article on the lowest common ancestor gives the details.

Common mistakes

• Building position by position, with i in the outer loop and k inside. The level 2 cell at position 1 needs the level 1 cell at position 3, which isn't built yet; with a table filled with zeros, every cell of levels 2 and 3 becomes 0, and the query 2 to 8 prints 0. Put k in the outer loop.

• Too few levels in a fixed-size table. int st[16][MAXN] with n = 10^5 has levels 0 to 15, but a query of 65 536 or more elements uses level 16 and reads outside the table. Use lg[n] + 1 levels.

Similar structures

Prefix sums answer sums and XORs of a fixed array with one subtraction and $O(n)$ memory.

A segment tree answers the minimum or the sum of a range in O(\log n) and also lets elements change, each change in O(\log n). Use it when the array changes between queries (practice problem 695): in a sparse table, changing one element can change up to about $n$ cells. On a fixed array the sparse table answers each query in $O(1)$ instead of O(\log n), which matters for practice problem 691 with 10^7 queries.

A monotonic queue finds the minimum of every window of one fixed length as the window slides left to right, in $O(n)$ total time and $O(n)$ memory. Use the sparse table when the ranges are arbitrary.

Practice