Why this matters when you build with AI
An AI tool will write a sparse table quickly, and the code usually compiles. The bug that matters most is a sum. A sparse table built for min gets pasted into a problem that asks for a sum, and the code returns numbers that are too large. It does not crash, and on a small sample the error may not show up at all.
The reason is overlap. The sparse table answers a query with two blocks that can share elements. That is harmless for min and gcd, because repeating an element does not change the answer. It is wrong for sums, because the shared elements are added twice. This lesson shows the failure with a real number, then shows the fix.
Every program here was compiled with g++ -O2 -std=c++17 on the machine that wrote the lesson, using g++ 15.2.0. The random tests check every range or pair against a brute force, and the outputs are copied from those runs. The sizes of the tables and the memory figures are arithmetic, and no memory was measured. No outside source was checked for this lesson.
The idea: a table of answers for blocks of length 2^k
A sparse table stores the answer for many blocks. Let a have n values. Define st[k][i] as the answer over the block of length 2^k that starts at i, so st[k][i] covers a[i] up to a[i + 2^k - 1]. Level 0 holds the values themselves, since a block of length 1 is one value. Each higher level is built from the level below it. A block of length 2^k is two blocks of length 2^(k-1) placed side by side:
st[k][i] = op(st[k - 1][i], st[k - 1][i + 2^(k-1)])
Here op is the operation, such as min. The table has about log2(n) levels, each with about n entries, so the build costs O(n log n) time and memory.
Worked example with a = [5, 2, 8, 6, 3, 6, 9, 1] and op = min. The Python run below builds the table and prints the size of each level. Level 0 has 8 entries, since every index starts a block of length 1. Level 1 has 7, since the last index cannot start a block of length 2. Level 2 has 5, and level 3 has 1, because only one block of length 8 fits. The first two levels of the table are:
level 0 (length 1): 5 2 8 6 3 6 9 1
level 1 (length 2): 2 2 6 3 3 6 1Level 1 at index 0 is min(5, 2) = 2, and at index 1 it is min(2, 8) = 2. The second value is 2 because the block starts at index 1, and it covers the values 2 and 8.
Answering a query in O(1) with two overlapping blocks
To answer min over the half-open range [l, r), first find the largest k such that 2^k fits in the range, which means 2^k <= r - l. Then cover the range with two blocks of length 2^k. The first block starts at l. The second block ends at r, so it starts at r - 2^k. Together they cover the whole range, and they can overlap in the middle.
Worked example: [0, 5) has length 5. The largest power of two that fits is 2^2 = 4, so k = 2. The two blocks are [0, 4) and [1, 5). Both cover the range, and they overlap on [1, 4).
The value of k comes from a precomputed table lg[len] = floor(log2(len)), which is built in O(n). Computing it with a loop per query would be O(log n) per query, so the table is part of the O(1) claim.
Here is the Python version. It is fast enough for small inputs and is input free, so the site can run it. It uses half-open ranges like the rest of this module:
Real output of that program:
levels: 4 sizes: [8, 7, 5, 1]
min[1,5): 2
min[0,8): 1
min[6,7): 9The query min[1,5) covers 2, 8, 6, 3 and its answer is 2. The query min[6,7) has length 1, so k = 0 and both blocks are the same single value, 9.
Why idempotent operations are the only case for overlap
An operation is idempotent when op(x, x) = x. Min, max and gcd are idempotent. Sum and XOR are not. Overlap is safe only for idempotent operations, because the shared elements are included twice in the two blocks, and an idempotent operation gives the same answer whether a value is included once or twice.
For min, a value in the overlap is counted in both blocks, but min(x, x) is x. For gcd, the same holds because gcd(x, x) = x. The gcd of a range does not depend on repeating a value.
For a sum, repetition changes the answer. The example below uses s = [1, 2, 3, 4, 5, 6, 7] and the range [0, 6), whose true sum is 1 + 2 + 3 + 4 + 5 + 6 = 21. The two overlapping blocks are [0, 4) and [2, 6). Their sums are 10 and 18, which add to 28. The overlap [2, 4) holds the values 3 and 4, and it was added twice. The program below printed both numbers:
true sum[0,6) = 21, two overlapping blocks give 28A sparse table for sums is therefore wrong. The disjoint sparse table below is the fix.
Range minimum and range gcd in C++
The template below works for any idempotent associative operation. The operation is passed as a function object, so the same code builds a minimum table and a gcd table:
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
// Sparse table for an idempotent, associative operation: op(x, x) = x, and op is associative.
// st[k][i] = op over a[i .. i + 2^k - 1].
template <typename T, typename F>
struct SparseTable {
int n;
F op;
vector<int> lg; // lg[len] = floor(log2(len))
vector<vector<T>> st;
SparseTable(const vector<T> &a, F f) : n((int)a.size()), op(f), lg(a.size() + 2, 0) {
for (int i = 2; i <= n; i++) lg[i] = lg[i / 2] + 1;
int K = lg[max(n, 1)] + 1;
st.assign(K, vector<T>(max(n, 1)));
for (int i = 0; i < n; i++) st[0][i] = a[i];
for (int k = 1; k < K; k++)
for (int i = 0; i + (1 << k) <= n; i++)
st[k][i] = op(st[k - 1][i], st[k - 1][i + (1 << (k - 1))]);
}
// Answer for the half-open range [l, r), with l < r.
// Two blocks of length 2^k, both inside [l, r), cover it and overlap in the middle.
T query(int l, int r) const {
int k = lg[r - l];
return op(st[k][l], st[k][r - (1 << k)]);
}
};
struct GcdOp {
int operator()(int a, int b) const { return std::gcd(a, b); }
};
struct MinOp {
int operator()(int a, int b) const { return min(a, b); }
};The worked example from main in the same program runs these tables on a small array:
vector<int> a = {5, 2, 8, 6, 3, 6, 9};
SparseTable<int, MinOp> mn(a, MinOp{});
printf("min[1,5) = %d\n", mn.query(1, 5)); // 2 8 6 3
printf("min[3,7) = %d\n", mn.query(3, 7)); // 6 3 6 9
vector<int> g = {12, 18, 30, 8, 20};
SparseTable<int, GcdOp> gt(g, GcdOp{});
printf("gcd[0,3) = %d\n", gt.query(0, 3)); // gcd(12, 18, 30) = 6
printf("gcd[2,5) = %d\n", gt.query(2, 5)); // gcd(30, 8, 20) = 2Real output of that run:
min[1,5) = 2
min[3,7) = 3
gcd[0,3) = 6
gcd[2,5) = 2The two gcd answers can be checked by hand. gcd(12, 18, 30) is 6, because 6 divides all three and no larger number does. gcd(30, 8, 20) is 2, because 2 divides all three and 4 does not divide 30.
Across 300 random arrays of length 1 to 40, the program compared every range [l, r), which is 85,904 ranges in total, and found no mismatch for either table. The brute force loops over the range and takes the min or gcd directly.
Disjoint sparse table for sums
A disjoint sparse table answers O(1) queries for any associative operation, including sums, by making the two parts of each query non-overlapping. The idea is to divide the array into blocks of size 2^lev at each level. Each block has a middle point. For every index in the left half of a block, the table stores the operation from that index to the middle. For every index in the right half, it stores the operation from the middle to that index.
A query [l, r] (inclusive, with l < r) has one useful fact. The highest bit where l and r differ determines the level. At that level, l is in the left half of its block and r is in the right half, because the bit is 0 for l and 1 for r. So the answer is the left part from l to the middle, combined with the right part from the middle to r. The two parts do not overlap.
Worked example with s = [1, 2, 3, 4, 5, 6, 7], padded to 8 with a zero. The query [0, 4] sums indices 0 to 4. Since 0 and 4 differ first at bit 2, the level has blocks of size 8, and the middle is index 4. The left part is 1 + 2 + 3 + 4 = 10, and the right part is 5. Their sum is 15. Nothing is counted twice.
The C++ version stores 64-bit values and uses 1-based levels so that level 0 is unused:
// Disjoint sparse table for an associative operation that is NOT idempotent (here: sum).
// Every level lev splits the array into blocks of size 2^lev. For an index i in the left half of
// its block, t[lev][i] = sum of b[i .. mid-1]. For an index i in the right half, t[lev][i] = sum of b[mid .. i].
// A query [l, r] (inclusive, l < r) is answered by one level, with the two parts never overlapping.
struct DisjointSparseSum {
int N, LOG;
vector<ll> base;
vector<vector<ll>> t;
explicit DisjointSparseSum(const vector<ll> &a) {
int n = (int)a.size();
LOG = 1;
while ((1 << LOG) < n) LOG++;
N = 1 << LOG;
base.assign(N, 0);
for (int i = 0; i < n; i++) base[i] = a[i];
t.assign(LOG + 1, vector<ll>(N, 0));
for (int lev = 1; lev <= LOG; lev++) {
int half = 1 << (lev - 1), size = 1 << lev;
for (int start = 0; start < N; start += size) {
int mid = start + half;
t[lev][mid - 1] = base[mid - 1];
for (int i = mid - 2; i >= start; i--) t[lev][i] = base[i] + t[lev][i + 1];
t[lev][mid] = base[mid];
for (int i = mid + 1; i < start + size; i++) t[lev][i] = t[lev][i - 1] + base[i];
}
}
}
// Sum over the inclusive range [l, r].
ll query(int l, int r) const {
if (l == r) return base[l];
int lev = 32 - __builtin_clz((unsigned)(l ^ r)); // highest differing bit, plus 1
return t[lev][l] + t[lev][r];
}
};The main of the test program ran this on the array above:
disjoint sum[0..4] = 15 (expected 15)The query uses l ^ r, the bitwise XOR of the two indices. Its highest set bit is the position where the two indices first differ. For 0 and 4, that is 100 in binary, which is bit 2. Adding 1 gives level 3, and blocks of size 2^3 = 8.
Across the same 300 random arrays, the program checked every range [l, r] for sums and found 85,904 ranges with no mismatch.
LCA through the Euler tour
The lowest common ancestor (LCA) of two vertices u and v in a rooted tree is the deepest vertex that is an ancestor of both. In a contest, many queries ask for it on a fixed tree, and the standard approach turns LCA into a range minimum query, which the sparse table answers in O(1).
The Euler tour lists the vertices in the order a depth-first walk visits them. A vertex is written when the walk enters it and again each time the walk returns to it from a child. A tree with n vertices gives a tour of 2n - 1 entries.
Worked example with the tree below, rooted at 0:
0
/ \
1 2
/ \ / \
3 4 5 6The tour is 0 1 3 1 4 1 0 2 5 2 6 2 0, which is 13 entries for 7 vertices. The first occurrence of each vertex is its earliest position in the tour: vertex 0 at 0, vertex 1 at 1, vertex 3 at 2, vertex 4 at 4, vertex 2 at 7, vertex 5 at 8, and vertex 6 at 10.
Take lca(3, 4). Their first occurrences are 2 and 4. Between positions 2 and 4 the tour holds vertices 3, 1 and 4. The entry with the smallest depth is vertex 1, at depth 1, so the LCA is 1. That is correct, since 1 is the parent of both.
Take lca(3, 6). The first occurrences are 2 and 10. The range includes position 6, which holds vertex 0 at depth 0. The smallest depth is 0, so the LCA is 0. That is also correct, because 3 is under 1 and 6 is under 2, and only the root is above both.
The C++ version builds the tour with an explicit stack instead of recursion. Recursion on a path with a million vertices can overflow the call stack, and an explicit stack avoids that. It stores (depth, vertex) pairs, so the minimum is taken over depth first:
// LCA through the Euler tour. The tour lists a vertex on entry and again after each child returns,
// so it has 2n - 1 entries. The LCA of u and v is the vertex with the smallest depth between
// their first occurrences. Depth is the key, so the table holds (depth, vertex) pairs.
struct PairMin {
pair<int, int> operator()(pair<int, int> a, pair<int, int> b) const { return min(a, b); }
};
struct LcaEuler {
int n;
vector<vector<int>> adj;
vector<int> first, depth, parent;
SparseTable<pair<int, int>, PairMin> rmq;
static vector<vector<int>> make_adj(int n, const vector<pair<int, int>> &edges) {
vector<vector<int>> adj(n);
for (auto [u, v] : edges) {
adj[u].push_back(v);
adj[v].push_back(u);
}
return adj;
}
static vector<pair<int, int>> build_tour(int n, const vector<vector<int>> &adj, vector<int> &first,
vector<int> &depth, vector<int> &parent) {
vector<pair<int, int>> items; // (depth, vertex) in tour order
vector<pair<int, size_t>> stk; // (vertex, index of next neighbour to try)
first.assign(n, -1);
depth.assign(n, 0);
parent.assign(n, -1);
stk.push_back({0, 0});
first[0] = 0;
items.push_back({0, 0});
while (!stk.empty()) {
int v = stk.back().first;
size_t idx = stk.back().second;
if (idx < adj[v].size()) {
stk.back().second++;
int u = adj[v][idx];
if (u == parent[v]) continue;
parent[u] = v;
depth[u] = depth[v] + 1;
first[u] = (int)items.size();
items.push_back({depth[u], u});
stk.push_back({u, 0});
} else {
stk.pop_back();
if (!stk.empty()) {
int p = stk.back().first;
items.push_back({depth[p], p});
}
}
}
return items;
}
LcaEuler(int n_, const vector<pair<int, int>> &edges)
: n(n_), adj(make_adj(n_, edges)), rmq(build_tour(n_, adj, first, depth, parent), PairMin{}) {}
int lca(int u, int v) const {
int l = first[u], r = first[v];
if (l > r) swap(l, r);
return rmq.query(l, r + 1).second;
}
};The main of the test program prints the first occurrences, the tour and four LCA answers for this tree:
first occurrence: 0:0 1:1 2:7 3:2 4:4 5:8 6:10
euler tour (vertex): 0 1 3 1 4 1 0 2 5 2 6 2 0
lca(3,4) = 1, lca(3,6) = 0, lca(5,6) = 2, lca(4,4) = 4The tour printed here matches the hand trace. Its length of 13 equals 2 * 7 - 1. The LCA values match the hand answers, and lca(4, 4) = 4 is correct because a vertex is its own ancestor.
The random check built 200 random trees with 1 to 30 vertices. Each tree was checked for all pairs (u, v) against a brute force that climbs parent pointers to a common vertex. That was 62,595 pairs in total, with no mismatch.
Complexity and memory
For a sparse table of n values with K = floor(log2(n)) + 1 levels, the build costs O(n log n) time. Each query is O(1). The memory is K * n values. For n = 10^6 with 32-bit int values, K = 20, which is 20 million values, or 80 MB by arithmetic. Check the memory limit before you pick the table for the largest input.
For the disjoint sparse table, the padded size is N = 2^LOG, and the table has LOG + 1 rows of N 64-bit values. For n = 10^6, N = 2^20 and LOG = 20, so the table holds 21 rows of 1,048,576 values, which is about 176 MB by arithmetic. This is large. Use it only when the operation needs it, and check the memory limit first.
The LCA table has 2n - 1 entries, so it costs a little more than an n-entry table. Each LCA query is O(1) after an O(n log n) build.
These figures are arithmetic from the table sizes. They are not measured memory use, which also includes the vectors' overhead and the program's own data.
Common mistakes and what they look like
The first mistake is using a plain sparse table for a sum. The symptom is an answer that is too large, and it changes with the size of the overlap. In the example earlier, the two blocks gave 28 for a true sum of 21. The code runs, the output is a number, and a small sample may still pass when the ranges are short.
The second mistake is mixing the range convention. The query code above takes [l, r), but the disjoint table takes [l, r]. Calling one with the other's arguments gives an answer for the wrong range, and it does not crash. Pick one convention for each structure and name it.
The third mistake is a wrong second block. With a half-open r, the second block must start at r - 2^k. Starting at r - 2^k + 1 moves the block one step to the right, which can cover an index past the end of the range. Here is a real run of that wrong formula in Python on a = [5, 7, 8, 6, 3, 9], the range [0, 4):
correct min[0,4): 5
buggy min[0,4): 3
true min: 5The buggy block includes the 3 at index 4, which is outside [0, 4). The answer is wrong whenever a value just past r is smaller than every value inside the range.
The fourth mistake is a table that was built for n values but queried with r above n. The symptom is reading past the vector, which may crash or may read stale numbers. Check 0 <= l < r <= n at the start of each query while you test.
The fifth mistake is an LCA that uses a tour without the return entries. A tour that writes each vertex only once has length n, and its minimum-depth range no longer lines up with the path between the two vertices. I did not run this variant, so the symptom is not measured here. The random check above would catch it, because it compares every pair against the parent-climbing brute force.
Hands-on exercise
Write a range minimum table and a range gcd table in C++17 using the template above or your own version. Test both against a brute force that loops over the range, on random arrays of length 1 to 40 and every range. Then build an LCA structure for a random tree with 30 vertices, and compare every pair with a brute force that climbs parents. Print the number of mismatches for each test. Use a fixed random seed so the run repeats.
Prompt for an AI tool:
Write C++17 code with three parts: a generic sparse table for an idempotent operation using half-open
ranges [l, r), a range gcd query built from it, and an LCA structure for a rooted tree that uses the
Euler tour and the sparse table for range minimum on (depth, vertex) pairs. Also write a brute force
for each part. Generate 300 random arrays of length 1 to 40 and check every range against the brute
force. Generate 200 random trees of 1 to 30 vertices with the root at 0 and check every pair. Print
the mismatch count for each. Use an explicit stack for the tour, not recursion.
A good answer has an O(n log n) build, O(1) queries, the second block starting at r - 2^k, a tour
of length 2n - 1 that writes the parent after each child returns, and no mismatches. Check that the
brute force does not reuse the table, that the tree generator makes a connected tree, and that the
query swaps the two first occurrences when the first is larger.Show the answer
The answer to check against is the code above. A correct run prints zero mismatches for every test. Here is what to look for in an answer that does not pass. These symptoms were reasoned out and not run in this lesson. If the tour has n entries instead of 2n - 1, the LCA answers can be wrong on some pairs. If the gcd table uses the second block at r - 2^k + 1, the gcd can be wrong on some ranges. If the random tree generator can create a cycle, the depth search may never end.
Practice
Work each problem on paper or in code before you open the answer. Use half-open ranges unless a problem says otherwise.
- Given
a = [18, 27, 12, 8], find the gcd over[0, 2)and over[1, 4). Hint: list the values in each range and find the largest number that divides all of them. - Explain why the plain sparse table is wrong for XOR, and give the answer it returns for
a = [1, 2, 4]on[0, 3). Hint: XOR of a value with itself is 0, and the true XOR of the three values is 1 xor 2 xor 4. - A sparse table for
n = 200000values of 32-bitintis built with all levels. Compute the number of levels and the memory in bytes. Hint:floor(log2(200000)) = 17. - The code below is meant to answer a half-open min query, but it has one wrong line. Find it and say what the correct line is. Hint: compare the second block's start with the rule in this lesson.
def query_min(table, l, r):
k = (r - l).bit_length() - 1
return min(table[k][l], table[k][r - (1 << k) + 1])- For the tree with edges
(0, 1),(1, 2),(1, 3), the Euler tour is0 1 2 1 3 1 0. Findlca(2, 3)from the tour. Hint: find the first occurrences and the smallest depth between them.
Show the answer
- Over
[0, 2)the values are 18 and 27, and their gcd is 9. Over[1, 4)the values are 27, 12 and 8. The only common divisor of 27 and 8 is 1, so the gcd is 1. - XOR is not idempotent, because
x xor x = 0. Fora = [1, 2, 4]on[0, 3), the two blocks are[0, 2)and[1, 3). Their XORs are1 xor 2 = 3and2 xor 4 = 6. Combining them gives3 xor 6 = 5, because the 2 was counted twice and cancelled. The true XOR is1 xor 2 xor 4 = 7. So the plain table returns 5, not 7. By the same argument, a disjoint table with XOR in place of sum gives 7. I did not run that variant. - The number of levels is
floor(log2(200000)) + 1 = 17 + 1 = 18. Each level has 200000 entries of 4 bytes, so the memory is18 * 200000 * 4 = 14,400,000bytes, which is about 14.4 MB by arithmetic. - The wrong line is
table[k][r - (1 << k) + 1]. For a half-open range, the second block starts atr - (1 << k). The correct line isreturn min(table[k][l], table[k][r - (1 << k)]). - The first occurrence of 2 is at position 2 and of 3 is at position 4. Positions 2 to 4 hold vertices 2, 1 and 3. The smallest depth is at vertex 1, so the LCA is 1. That is correct, since 1 is the parent of both.
Summary
A sparse table answers range queries in O(1) after an O(n log n) build, by covering each range with two blocks of the same length. The overlap is safe for min and gcd and unsafe for sums, so sums need a disjoint table, which splits each query into two parts that do not overlap. LCA becomes a range minimum on the Euler tour, and the tour has 2n - 1 entries. Check every structure against a brute force on random inputs and check the memory against the limit before the largest input.