sparse_table

Sparse Table

Sparse table is a data structure that can help us answer range queries on a set on static data (i.e. data that does not change regularly).
Sparse table does pre-processing on the data first, then it can answer range queries efficiently.

More formally, sparse table can calculate the answer of Q(l, r) on an array a[i] of length n.
Where Q(l, r) can be any duplicate-invariant function as...

• max
• min
• GCD
• LCM

What I mean by duplicate-invariant function is any function that output the same value for duplicate inputs.
So for example:

Function	Description
min(2, 3) = min(2, 2, 3, 3) = 2	minimum is duplicate-invariant function
(2 + 3) != (2 + 2 + 3 + 3)	addition is not duplicate-invariant.

Sparse Table Structure

The structure of sparse table is a 2D array ST[j][i],
where the j-th row in the sparse table holds the answer of queries of length 2^j.

More formally, ST[j][i] holds the value of Q(i, i + (2^j) - 1)

We can build the sparse table easily in O(n.log(n)) as follows (having Q() equals min() as an example):

for (int i = 0; i < n; ++i) {
    ST[0][i] = a[i];
}

// Note that (1 << j) is equivalent to pow(2, j)

for (int j = 1; (1 << j) <= n; ++j) {
    for (int i = 0; (i + (1 << j)) <= n; ++i) {
        int x = ST[j - 1][i];
        int y = ST[j - 1][i + (1 << (j - 1))];

        ST[j][i] = min(x, y);
    }
}

Sparse Table Query

Now in order to calculate any Q(l, r) we are going to use the duplicate-invariant property to get the answer in O(1) as follows:

// LOG is a pre-computed array where LOG[i] = floor(log2(i))

int g = LOG[r - l + 1];

int x = ST[g][l];
int y = ST[g][r - (1 << g) + 1];

return min(x, y);

Full Implementation

You can find the full implementation of the sparse table here.

The above implementation is an example of sparse table the computes the index of the minimum element in the range [L, R]

Problems

1. Codeforces CGCDSSQ => Solution