# 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 tables allow us to answer an answer any minimum/maximum query in $O(1)$ time after $O(ngn)$ 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,g$ and $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})$ (we can also write $[i,i+2_{j−1}−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])$

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

`MAXN`

→ N+1 ?- For arrays with reasonable length ($≤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

**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]),wherej=g_{2}(R−L+1)$

This requires that we are able to compute $g_{2}(R−L+1)$ fast. You can accomplish that by precomputing all logarithms.