Sparse table
Sparse Table is a data structure for processing range queries on a static array (the array does not change).
Most often used for:
After preprocessing:
Any number can be represented as a sum of powers of two:
The same can be done with the length of a segment.
Any segment can be represented as the union of two overlapping segments of length :
For idempotent operations (min, max, gcd) this works perfectly.
Let’s create a table:
where:
i — the start of the segmentj — the power of twotable[i][j] stores the answer on a segment of length starting at iFor this type, will be defined as . The table will be built as follows:
To answer a query for the range , we need to go through all powers of two (starting from the highest). If , we have found the first part of the range and can continue with the remaining range .
A sparse table answers this kind of query best with complexity. The idea is that unlike sum queries, the minimum does not require the ranges to be non-overlapping, so instead of splitting into non-overlapping ranges in , we can simply split the range into 2 overlapping ranges of length a power of 2.
For example, consider the range . It can be split into and , which overlap at 7.
To answer a range query from to , we find the largest such that and return the minimum of table[L][j] and table[R - 2^j + 1][j].
Preprocessing: , where is the size of the array.
It is required to compute values for all segments of length .
Answering a query:
Memory: — the table for all powers of two is stored.
A sparse table is effective when:
const int MAXN = 100000;
const int LOG = 20;
int table[MAXN][LOG];
int lg[MAXN];
int f(int a, int b) {
return min(a, b); // can be replaced with max, gcd, etc.
}
void buildSparseTable(int arr[], int N) {
// precompute logarithms
lg[1] = 0;
for (int i = 2; i <= N; i++) {
lg[i] = lg[i / 2] + 1;
}
// initialization for length 1
for (int i = 0; i < N; i++) {
table[i][0] = arr[i];
}
// dynamic building
for (int j = 1; (1 << j) <= N; j++) {
for (int i = 0; i + (1 << j) <= N; i++) {
table[i][j] = f(
table[i][j - 1],
table[i + (1 << (j - 1))][j - 1]
);
}
}
}
void buildSparseTable(int arr[], int N) {
for (int i = 0; i < N; i++) {
table[i][0] = arr[i];
}
for (int j = 1; (1 << j) <= N; j++) {
for (int i = 0; i + (1 << j) <= N; i++) {
table[i][j] = table[i][j - 1] + table[i + (1 << (j - 1))][j - 1];
}
}
}
long long sum = 0;
// 2^25 is usually enough in most problems
for (int i = 25; i >= 0; i--) {
if ((1 << i) <= R - L + 1) {
sum += table[L][i];
L += (1 << i);
}
}
int query(int L, int R) {
int j = (int)log2(R - L + 1);
return min(table[L][j], table[R - (1 << j) + 1][j]);
}