PK

PKBytes

Explore tracks
Chapter 30: Static Range Queries and Decomposition Techniques
30.01Intermediate / Advanced5 topics15 min5 interactive animations

Sparse table

A sparse table answers range minimum, maximum and GCD queries in O(1) after O(n log n) preprocessing, by covering any range with two overlapping power-of-two blocks.

Learning goals

  • Explain why the overlap of two blocks is harmless for min, max and GCD but not for sums
  • Build the table level by level from the level below
  • Precompute floor(log2) values or use Integer.numberOfLeadingZeros
  • Answer range minimum queries in O(1), returning either the value or the index

Prerequisites

ArraysPrefix sumsBit manipulationSegment tree fundamentals

A segment tree answers a range minimum in O(log n). If the array never changes and there are millions of queries, paying O(n log n) once to make every query two table reads is a much better deal.

30.01.1

Idempotent operations

An operation is **idempotent** if applying it to the same value twice changes nothing: op(x, x) = x. Minimum, maximum, GCD, bitwise AND and OR are idempotent; sum, product and XOR are not. The sparse table's trick only works for idempotent operations, because it covers a range by two blocks that may overlap and so counts the overlapping values twice.

Open the animation's preset "Sum goes wrong (overlap)": the same two overlapping blocks give 46 instead of the true 26, because three positions are counted twice. For a minimum the same overlap is harmless, since min(x, x) = x. If your operation is not idempotent, use the disjoint sparse table of the next lesson.

Operationop(x, x)Idempotent?Sparse table works?
minimum / maximumxyesyes
GCDxyesyes
AND / ORxyesyes
sum2xnono (double counts)
XOR0nono (cancels)
productx²nono
Java
1static long sumByTwoBlocks(int[] a, int l, int r) {      // WRONG for sums: shows what the overlap does
2    int k = 31 - Integer.numberOfLeadingZeros(r - l + 1);
3    long left = 0, right = 0;
4    for (int i = l; i < l + (1 << k); i++) left += a[i];
5    for (int i = r - (1 << k) + 1; i <= r; i++) right += a[i];
6    return left + right;                         // counts the positions in both blocks twice
7}

Sparse table: O(1) range queries from two overlapping blocks

Interactive · edit the input

Your input

Try

level 0: min of 1 value starting at i

50
21
82
33
94
45
76
67
Setup

Level 0 is the array itself. Level k holds the min of every block of 2^k consecutive values, and only 4 levels are needed because 2^3 ≤ 8.

Step 1 / 7
Java
1int[][] st;                                      // st[k][i] = op over a[i .. i + 2^k - 1]
2void build(int[] a) {
3    int n = a.length, K = 32 - Integer.numberOfLeadingZeros(n);
4    st = new int[K][n];
5    st[0] = a.clone();
6    for (int k = 1; k < K; k++)
7        for (int i = 0; i + (1 << k) <= n; i++)
8            st[k][i] = Math.min(st[k - 1][i], st[k - 1][i + (1 << (k - 1))]);   // two halves of the block
9}
10int query(int l, int r) {                        // inclusive
11    int k = 31 - Integer.numberOfLeadingZeros(r - l + 1);   // floor(log2(length))
12    return Math.min(st[k][l], st[k][r - (1 << k) + 1]);     // two blocks that may overlap
13}

Live state

0 cells computed

n

8

levels

4

No condition evaluated on this step
Execution trace (dry run table)Show 7 steps
StepLineStateWhat happens
1L5n=8 levels=4Level 0 is the array itself. Level k holds the min of every block of 2^k consecutive values, and only 4 levels are needed because 2^3 ≤ 8.
2L8k=1 block length=2 cells=7Level 1: each cell combines two adjacent cells of level 0, st[1][i] = min(st[0][i], st[0][i + 1]). 7 cells computed.
3L8k=2 block length=4 cells=5Level 2: each cell combines two adjacent cells of level 1, st[2][i] = min(st[1][i], st[1][i + 2]). 5 cells computed.
4L8k=3 block length=8 cells=1Level 3: each cell combines two adjacent cells of level 2, st[3][i] = min(st[2][i], st[2][i + 4]). 1 cell computed.
5L11l=1 r=5 length=5 k=2Query [1, 5]: length 5, so k = floor(log2 5) = 2. Two blocks of 4 values cover the range: one starting at l = 1, one ending at r = 5.
6L12st[k][l]=2 st[k][r-2^k+1]=3 min=2 overlap=3Left block [1, 4] gives 2, right block [2, 5] gives 3. They overlap on 3 positions.
7L12return=2min(a[1..5]) = 2, from two table reads: O(1) per query after an O(n log n) build. Counting a position twice cannot change a min.
30.01.2

Min/max/GCD

The table has one row per level. Level k stores, for every start i with i + 2^k <= n, the answer for the block of 2^k values starting at i. Level 0 is the array. Each cell of level k combines two adjacent cells of level k - 1: st[k][i] = op(st[k-1][i], st[k-1][i + 2^(k-1)]). Passing the operation as a parameter gives one class for min, max, GCD, AND and OR.

The build costs O(n log n) time and space: about n cells per level and ⌊log2 n⌋ + 1 levels. In the preset "Range GCD" (12 18 8 24 36 9 6 30) the animation builds 4 levels, and the query over positions 0 to 4 returns 2 from two blocks of length 4.

Java
1class SparseTable {
2    private final int[][] st;
3    private final IntBinaryOperator op;          // must be associative and idempotent
4    SparseTable(int[] a, IntBinaryOperator op) {
5        this.op = op;
6        int n = a.length, K = 32 - Integer.numberOfLeadingZeros(n);
7        st = new int[K][];
8        st[0] = a.clone();
9        for (int k = 1; k < K; k++) {
10            st[k] = new int[n - (1 << k) + 1];
11            for (int i = 0; i + (1 << k) <= n; i++)
12                st[k][i] = op.applyAsInt(st[k - 1][i], st[k - 1][i + (1 << (k - 1))]);   // two halves of the block
13        }
14    }
15    int query(int l, int r) {                    // inclusive, 0-based
16        int k = 31 - Integer.numberOfLeadingZeros(r - l + 1);
17        return op.applyAsInt(st[k][l], st[k][r - (1 << k) + 1]);
18    }
19}

Sparse table: O(1) range queries from two overlapping blocks

Interactive · edit the input

Your input

Try

level 0: min of 1 value starting at i

50
21
82
33
94
45
76
67
Setup

Level 0 is the array itself. Level k holds the min of every block of 2^k consecutive values, and only 4 levels are needed because 2^3 ≤ 8.

Step 1 / 7
Java
1int[][] st;                                      // st[k][i] = op over a[i .. i + 2^k - 1]
2void build(int[] a) {
3    int n = a.length, K = 32 - Integer.numberOfLeadingZeros(n);
4    st = new int[K][n];
5    st[0] = a.clone();
6    for (int k = 1; k < K; k++)
7        for (int i = 0; i + (1 << k) <= n; i++)
8            st[k][i] = Math.min(st[k - 1][i], st[k - 1][i + (1 << (k - 1))]);   // two halves of the block
9}
10int query(int l, int r) {                        // inclusive
11    int k = 31 - Integer.numberOfLeadingZeros(r - l + 1);   // floor(log2(length))
12    return Math.min(st[k][l], st[k][r - (1 << k) + 1]);     // two blocks that may overlap
13}

Live state

0 cells computed

n

8

levels

4

No condition evaluated on this step
Execution trace (dry run table)Show 7 steps
StepLineStateWhat happens
1L5n=8 levels=4Level 0 is the array itself. Level k holds the min of every block of 2^k consecutive values, and only 4 levels are needed because 2^3 ≤ 8.
2L8k=1 block length=2 cells=7Level 1: each cell combines two adjacent cells of level 0, st[1][i] = min(st[0][i], st[0][i + 1]). 7 cells computed.
3L8k=2 block length=4 cells=5Level 2: each cell combines two adjacent cells of level 1, st[2][i] = min(st[1][i], st[1][i + 2]). 5 cells computed.
4L8k=3 block length=8 cells=1Level 3: each cell combines two adjacent cells of level 2, st[3][i] = min(st[2][i], st[2][i + 4]). 1 cell computed.
5L11l=1 r=5 length=5 k=2Query [1, 5]: length 5, so k = floor(log2 5) = 2. Two blocks of 4 values cover the range: one starting at l = 1, one ending at r = 5.
6L12st[k][l]=2 st[k][r-2^k+1]=3 min=2 overlap=3Left block [1, 4] gives 2, right block [2, 5] gives 3. They overlap on 3 positions.
7L12return=2min(a[1..5]) = 2, from two table reads: O(1) per query after an O(n log n) build. Counting a position twice cannot change a min.
30.01.3

Precompute powers of two

A query needs k = floor(log2(length)). In Java the cheapest way is 31 - Integer.numberOfLeadingZeros(length), a single CPU instruction. A lookup table is the classic alternative that works in any language: lg[1] = 0 and lg[i] = lg[i / 2] + 1, computed once in O(n). Both give the same values, so use the built-in unless a table is clearer in your context.

The number of levels is floor(log2 n) + 1, which is 32 - Integer.numberOfLeadingZeros(n). For n = 8 that is 4 levels (blocks of 1, 2, 4 and 8); for n = 1 it is 1. Memory is the real limit of the structure: 10^6 values need 20 levels of up to 10^6 ints, about 80 MB.

n12347810001,000,000
levels = ⌊log2 n⌋ + 11223341020
Java
1static int[] logTable(int n) {                   // lg[i] = floor(log2 i) for i in 1..n
2    int[] lg = new int[n + 1];
3    for (int i = 2; i <= n; i++) lg[i] = lg[i / 2] + 1;
4    return lg;
5}
6static int levels(int n) { return 32 - Integer.numberOfLeadingZeros(n); }

Sparse table: O(1) range queries from two overlapping blocks

Interactive · edit the input

Your input

Try

level 0: min of 1 value starting at i

50
21
82
33
94
45
76
67
Setup

Level 0 is the array itself. Level k holds the min of every block of 2^k consecutive values, and only 4 levels are needed because 2^3 ≤ 8.

Step 1 / 7
Java
1int[][] st;                                      // st[k][i] = op over a[i .. i + 2^k - 1]
2void build(int[] a) {
3    int n = a.length, K = 32 - Integer.numberOfLeadingZeros(n);
4    st = new int[K][n];
5    st[0] = a.clone();
6    for (int k = 1; k < K; k++)
7        for (int i = 0; i + (1 << k) <= n; i++)
8            st[k][i] = Math.min(st[k - 1][i], st[k - 1][i + (1 << (k - 1))]);   // two halves of the block
9}
10int query(int l, int r) {                        // inclusive
11    int k = 31 - Integer.numberOfLeadingZeros(r - l + 1);   // floor(log2(length))
12    return Math.min(st[k][l], st[k][r - (1 << k) + 1]);     // two blocks that may overlap
13}

Live state

0 cells computed

n

8

levels

4

No condition evaluated on this step
Execution trace (dry run table)Show 7 steps
StepLineStateWhat happens
1L5n=8 levels=4Level 0 is the array itself. Level k holds the min of every block of 2^k consecutive values, and only 4 levels are needed because 2^3 ≤ 8.
2L8k=1 block length=2 cells=7Level 1: each cell combines two adjacent cells of level 0, st[1][i] = min(st[0][i], st[0][i + 1]). 7 cells computed.
3L8k=2 block length=4 cells=5Level 2: each cell combines two adjacent cells of level 1, st[2][i] = min(st[1][i], st[1][i + 2]). 5 cells computed.
4L8k=3 block length=8 cells=1Level 3: each cell combines two adjacent cells of level 2, st[3][i] = min(st[2][i], st[2][i + 4]). 1 cell computed.
5L11l=1 r=5 length=5 k=2Query [1, 5]: length 5, so k = floor(log2 5) = 2. Two blocks of 4 values cover the range: one starting at l = 1, one ending at r = 5.
6L12st[k][l]=2 st[k][r-2^k+1]=3 min=2 overlap=3Left block [1, 4] gives 2, right block [2, 5] gives 3. They overlap on 3 positions.
7L12return=2min(a[1..5]) = 2, from two table reads: O(1) per query after an O(n log n) build. Counting a position twice cannot change a min.
30.01.4

O(1) RMQ

A **range minimum query** (RMQ) asks for the minimum of a[l..r]. With the sparse table it takes two reads and one comparison: let k = floor(log2(r - l + 1)) and return min(st[k][l], st[k][r - 2^k + 1]). The two blocks both lie inside [l, r] and together cover it, because each has length at least half of the range.

Often you need the position of the minimum, not only its value. Store indices instead of values and compare through the array; with <= for the left block the leftmost minimum wins. The preset "Range minimum" in the animation answers [1, 5] of 5 2 8 3 9 4 7 6 with 2, using blocks of length 4 starting at 1 and ending at 5.

Java
1class RangeMin {
2    private final int[] a;
3    private final int[][] idx;                   // idx[k][i]: index of the minimum of a[i .. i + 2^k - 1]
4    RangeMin(int[] values) {
5        a = values.clone();
6        int n = a.length, K = 32 - Integer.numberOfLeadingZeros(n);
7        idx = new int[K][];
8        idx[0] = new int[n];
9        for (int i = 0; i < n; i++) idx[0][i] = i;
10        for (int k = 1; k < K; k++) {
11            idx[k] = new int[n - (1 << k) + 1];
12            for (int i = 0; i + (1 << k) <= n; i++) {
13                int x = idx[k - 1][i], y = idx[k - 1][i + (1 << (k - 1))];
14                idx[k][i] = a[x] <= a[y] ? x : y;        // ties keep the left index
15            }
16        }
17    }
18    int argMin(int l, int r) {
19        int k = 31 - Integer.numberOfLeadingZeros(r - l + 1);
20        int x = idx[k][l], y = idx[k][r - (1 << k) + 1];
21        return a[x] <= a[y] ? x : y;
22    }
23    int min(int l, int r) { return a[argMin(l, r)]; }
24}

Sparse table: O(1) range queries from two overlapping blocks

Interactive · edit the input

Your input

Try

level 0: min of 1 value starting at i

50
21
82
33
94
45
76
67
Setup

Level 0 is the array itself. Level k holds the min of every block of 2^k consecutive values, and only 4 levels are needed because 2^3 ≤ 8.

Step 1 / 7
Java
1int[][] st;                                      // st[k][i] = op over a[i .. i + 2^k - 1]
2void build(int[] a) {
3    int n = a.length, K = 32 - Integer.numberOfLeadingZeros(n);
4    st = new int[K][n];
5    st[0] = a.clone();
6    for (int k = 1; k < K; k++)
7        for (int i = 0; i + (1 << k) <= n; i++)
8            st[k][i] = Math.min(st[k - 1][i], st[k - 1][i + (1 << (k - 1))]);   // two halves of the block
9}
10int query(int l, int r) {                        // inclusive
11    int k = 31 - Integer.numberOfLeadingZeros(r - l + 1);   // floor(log2(length))
12    return Math.min(st[k][l], st[k][r - (1 << k) + 1]);     // two blocks that may overlap
13}

Live state

0 cells computed

n

8

levels

4

No condition evaluated on this step
Execution trace (dry run table)Show 7 steps
StepLineStateWhat happens
1L5n=8 levels=4Level 0 is the array itself. Level k holds the min of every block of 2^k consecutive values, and only 4 levels are needed because 2^3 ≤ 8.
2L8k=1 block length=2 cells=7Level 1: each cell combines two adjacent cells of level 0, st[1][i] = min(st[0][i], st[0][i + 1]). 7 cells computed.
3L8k=2 block length=4 cells=5Level 2: each cell combines two adjacent cells of level 1, st[2][i] = min(st[1][i], st[1][i + 2]). 5 cells computed.
4L8k=3 block length=8 cells=1Level 3: each cell combines two adjacent cells of level 2, st[3][i] = min(st[2][i], st[2][i + 4]). 1 cell computed.
5L11l=1 r=5 length=5 k=2Query [1, 5]: length 5, so k = floor(log2 5) = 2. Two blocks of 4 values cover the range: one starting at l = 1, one ending at r = 5.
6L12st[k][l]=2 st[k][r-2^k+1]=3 min=2 overlap=3Left block [1, 4] gives 2, right block [2, 5] gives 3. They overlap on 3 positions.
7L12return=2min(a[1..5]) = 2, from two table reads: O(1) per query after an O(n log n) build. Counting a position twice cannot change a min.
30.01.5

Overlapping blocks

Why two blocks are enough: the longest power of two not above the length, 2^k, satisfies 2^k <= length < 2^(k+1). A block of 2^k starting at l and another ending at r together cover [l, r], because their total length 2 × 2^k is at least length. They overlap in 2^(k+1) - length positions, at least one, and exactly 2^k when the length is a power of two (then both are the same block).

For a non-idempotent operation you can still use a sparse table, but only with the binary decomposition of the length: take the largest block at l, move l forward by its size, and repeat. That costs O(log n) per query instead of O(1), the same as a Fenwick tree, so it is rarely worth the memory.

Java
1static long[][] buildSums(int[] a) {             // st[k][i] = sum of a[i .. i + 2^k - 1]
2    int n = a.length, K = 32 - Integer.numberOfLeadingZeros(n);
3    long[][] st = new long[K][];
4    st[0] = new long[n];
5    for (int i = 0; i < n; i++) st[0][i] = a[i];
6    for (int k = 1; k < K; k++) {
7        st[k] = new long[n - (1 << k) + 1];
8        for (int i = 0; i + (1 << k) <= n; i++) st[k][i] = st[k - 1][i] + st[k - 1][i + (1 << (k - 1))];
9    }
10    return st;
11}
12static long sumByDecomposition(long[][] st, int l, int r) {      // O(log n): disjoint blocks, one per set bit of the length
13    long total = 0;
14    for (int k = st.length - 1; k >= 0; k--) {
15        if ((1 << k) <= r - l + 1) { total += st[k][l]; l += 1 << k; }
16    }
17    return total;
18}

Sparse table: O(1) range queries from two overlapping blocks

Interactive · edit the input

Your input

Try

level 0: min of 1 value starting at i

50
21
82
33
94
45
76
67
Setup

Level 0 is the array itself. Level k holds the min of every block of 2^k consecutive values, and only 4 levels are needed because 2^3 ≤ 8.

Step 1 / 7
Java
1int[][] st;                                      // st[k][i] = op over a[i .. i + 2^k - 1]
2void build(int[] a) {
3    int n = a.length, K = 32 - Integer.numberOfLeadingZeros(n);
4    st = new int[K][n];
5    st[0] = a.clone();
6    for (int k = 1; k < K; k++)
7        for (int i = 0; i + (1 << k) <= n; i++)
8            st[k][i] = Math.min(st[k - 1][i], st[k - 1][i + (1 << (k - 1))]);   // two halves of the block
9}
10int query(int l, int r) {                        // inclusive
11    int k = 31 - Integer.numberOfLeadingZeros(r - l + 1);   // floor(log2(length))
12    return Math.min(st[k][l], st[k][r - (1 << k) + 1]);     // two blocks that may overlap
13}

Live state

0 cells computed

n

8

levels

4

No condition evaluated on this step
Execution trace (dry run table)Show 7 steps
StepLineStateWhat happens
1L5n=8 levels=4Level 0 is the array itself. Level k holds the min of every block of 2^k consecutive values, and only 4 levels are needed because 2^3 ≤ 8.
2L8k=1 block length=2 cells=7Level 1: each cell combines two adjacent cells of level 0, st[1][i] = min(st[0][i], st[0][i + 1]). 7 cells computed.
3L8k=2 block length=4 cells=5Level 2: each cell combines two adjacent cells of level 1, st[2][i] = min(st[1][i], st[1][i + 2]). 5 cells computed.
4L8k=3 block length=8 cells=1Level 3: each cell combines two adjacent cells of level 2, st[3][i] = min(st[2][i], st[2][i + 4]). 1 cell computed.
5L11l=1 r=5 length=5 k=2Query [1, 5]: length 5, so k = floor(log2 5) = 2. Two blocks of 4 values cover the range: one starting at l = 1, one ending at r = 5.
6L12st[k][l]=2 st[k][r-2^k+1]=3 min=2 overlap=3Left block [1, 4] gives 2, right block [2, 5] gives 3. They overlap on 3 positions.
7L12return=2min(a[1..5]) = 2, from two table reads: O(1) per query after an O(n log n) build. Counting a position twice cannot change a min.

Practice ladder

Now try it yourself

Easy

  • Range Sum Query - Immutable

Medium

  • Sliding Window Maximum
  • Longest Continuous Subarray With Absolute Diff Less Than or Equal to Limit

Advanced

  • Static Range Minimum Queries (CSES)
  • Static RMQ (Library Checker)

Key takeaways

  • Level k holds the answer for every block of 2^k values; each cell combines two cells of the level below.
  • Two overlapping blocks cover any range, so a query is two reads: O(1), but only for idempotent operations.
  • Preprocessing costs O(n log n) time and memory; use it for static arrays with many queries.