Sparse Table

Problems: https://codeforces.com/blog/entry/70418

Resources

• https://cp-algorithms.com/data_structures/sparse-table.html
• https://brilliant.org/wiki/sparse-table/
• Geeks for Geeks (talks about Sparse table applied to GCD)
• Sparse Table & RMQ (Range Minimum Query) by Errichto

Sparse tables allow us to answer an answer any minimum/maximum query in $O(1)$ time after $O(n\log n)$ time preprocessing method.

The main idea behind Sparse Tables is to precompute all answers for range queries with power of two length.

I think I finally start to get it! I will use the $\min$ function as template, but you can easily apply it to $\max ,\gcd$ and $\text{lcm}$, and even SUM (but you need to be careful with the query logic since you cannot overlap).

Building the Table  $st[i][j]$ will store the answer starting at $i$ and of length $2^j$, thus the range $[i,i+2^j-1])$.

To build the table, we use DP and construct $st[i][j]$ (of length $2^j$) from the two smaller arrays of size $2^{j-1}$ (which we have already computed): $st[i][j]=\min (st[i][j-1],st[i+2^{j-1}][j-1])$

• this is the min of the intervals
• left is $[i,i+2^{j-1}-1]$
• right is $[i+2^{j-1},i+2^j-1]$

So how big should the sparse table be? st[MAXN][K+1]

• MAXN → N+1 ?
• For arrays with reasonable length ($\le 10^7$ elements), $K=25$ is a good value, since $2^{25}=33554432>10^7$ → Trick to remember, K+1 = 26 letters in the alphabet

int st[MAXN][K + 1];
// Generating the table, where the function f depends on the type of query
for (int i = 0; i < N; i++) {
    st[i][0] = array[i];
}
 
// Build the sparse table with DP
for (int j = 1; j <= K; j++) {
    for (int i = 0; i + (1 << j) <= N; i++) {
        st[i][j] = min(st[i][j-1], st[i + (1 << (j - 1))][j - 1]);
    }
}

• From cp-algorithms

Answering Queries Range query can be answered by splitting the range into ranges with power of two lengths, looking up the precomputed answers, and combining them to receive a complete answer.

For Range minimum/maximum/gcd/lcm query, you can just do this step once, splitting it into two ranges, because overlapping ranges do not affect the answer (IMPORTANT: this is NOT the case for sum queries).

So we can compute the minimum of the range $[L,R]$ with: $\min (st[L][j],st[R-2^j+1][j]),\text{where }j={\log }_2(R-L+1)$

This requires that we are able to compute ${\log }_2(R-L+1)$ fast. You can accomplish that by precomputing all logarithms.

// First precompute all logs
int lg[MAXN+1];
lg[1] = 0;
for (int i = 2; i <= MAXN; i++) {
    lg[i] = lg[i/2] + 1;
}
 
// USE CODE ABOVE: Build the sparse table, where f(x,y) =  min(x,y)
 
 
// Compute the minimum in range [L,R]:
int query(int L, int R) {
	int j = lg[R - L + 1];
	return min(st[L][j], st[R - (1 << j) + 1][j]);
}

Related

• Lowest Common Ancestor