sparse_table.md

What are sparse tables?

• Data structure that allows range queries
• Can answer most queries in O(log N)
• But can answer Range Minimum Queries in O(1)
  • An idempotent operation can be repeated an arbitrary number of times and the result will be the same as if it had been done only once. In arithmetic, adding zero to a number is idempotent.
• It can be only used on immutable arrays. If you need any change, whole DS needs to be changed

Intuition

• Any non negative number can be uniquely represented as a sum of decreasing powers of 2. This is just a variant of binary representation of a number. For number x, there can be at most log2(x) summands
• So, by the same reasoning, any interval can be represented as a union of intervals with lengths that are decreasing powers of two. Eq.. [2, 14] = [2, 9] U [10, 13] U [14, 14]
• And hence, also here union consists of at most [log2(length of interval)] many intervals.
• MAIN IDEA: Pre-compute all answers for range queries with power of 2 length. So, afterwards combining all of them to receive a complete answer.

Precomputation

• We will maintain a 2D array
• Where table[i][j] will store the answer for the range [i, i + 2^j - 1] which can be split nicely into ranges
  • [i, i + 2^{j-1} - 1] and [i + 2^(j-1), i + 2^j - 1] both of length 2^{j-1}
  • So, we can generate this table with dynamic programming

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

• for sum (between L and R)

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

• for RMQ (Minimum between L and R)

int j = log[R - L + 1];
int minimum = min(table[L][j], table[R - (1 << j) + 1][j]);