Sparse Table


Sparse tables allow us to answer an answer any minimum/maximum query in time after 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 function as template, but you can easily apply it to and , and even SUM (but you need to be careful with the query logic since you cannot overlap).

Building the Table   will store the answer starting at and of length , thus the range  (we can also write .

To build the table, we use DP and construct (of length ) from the two smaller arrays of size (which we have already computed):

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

  • MAXN N+1 ?
  • For arrays with reasonable length ( elements),  is a good value, since 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]);

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  with:

This requires that we are able to compute  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]);