Sparse tables

Follow @sukeesh

What are sparse tables?

Intuition

Precomputation

K = log2(MAXN) + 1

logarithmic values

int log[MAXN+1];
log[1] = 0;
for (int i = 2; i <= MAXN; i++)
    log[i] = log[i/2] + 1;

computing sparse table

for (int i = 0; i < MAXN; i++)
    table[i][0] = f(array[i]);

for (int j = 1; j <= K; j++)
    for (int i = 0; i + (1 << j) <= MAXN; i++)
        table[i][j] = f(table[i][j-1], table[i + (1 << (j - 1))][j - 1]);

Query

int sum = 0;
for (int j = K; j >= 0; j--) {
    if ((1 << j) <= R - L + 1) {
        sum += table[L][j];
        L += 1 << j;
    }
}
int j = log[R - L + 1];
int minimum = min(table[L][j], table[R - (1 << j) + 1][j]);