Some thoughts around sparse tables

References

• https://cp-algorithms.com/data_structures/sparse-table.html
• Problems:
• https://codeforces.com/blog/entry/70418
• Very good : https://codeforces.com/blog/entry/101083
• https://codeforces.com/blog/entry/75611
• There is something called as a [[Disjoint sparse trees]] as well

Details

What's the main idea?

The major use case that sparse tables solve is the range minimum query - for an immutable array, in $O(1)$ time.

The main idea behind that is : If I want to get the minimum of a range say $[L,R]$ = then that's equivalent to saying $min(min(L, L + k), min(R - k + 1, R))$ where $k \geq \frac{L + R} {2}$. This is because even if some middle elements in the range are common in both the ranges, the output still remains correct.

If you've this minimum of sub-ranges already pre-calculated for ks of appropriate size, then this operation can be done in $O(1)$ time.
 

How's the pre-calculation done here?

We can keep ranges like this:
- For every index inside the array - we keep the minimums for all powers of 2 (only until it makes sense, that is at max $log_2(n)$ where $n$ is the size of the array).

So let's say we have an array like this : [1, 2, 9, 4, 11]

Here, if we are talking from the perspective of index = 1, which is 2, then we will keep:

• Range of size 1 ( $= 2^0$ ) from index = 1, has min = 2 (only 2 in the current range)
• Range of size 2 ($=2^1$) from index = 1, has min = 2 (2 and 9 in the current range)
• Range of size 4 ($=2^2$) from index = 1, has min = 2 (2, 9, 4 and 11 in the current range)
• Range of size 8 - not possible, as array size itself is just 5.

We save this information for all the indexes of the array. This, therefore is saved inside a 2-D matrix. Let's call this matrix $st$, where $st[i][j]$ = minimum for the range from index $i$ of size $2^j$

Therefore note that $st[i][0]$ will just be the array itself.

Now we can calculate this easily by noticing that for a range of size 4, you can get the answer from ranges of sizes 2. That is for min of [a, b, c, d], you can use the min of [a, b] and [c, d].

Therefore we can calculate each power of 2 level-wise, and use that to calculate the next level.

Therefore we can say:

$$ st[i][j] = min(st[i][j - 1], st[i + (1<<(j - 1))][j - 1]) $$

This just means that for the range of size $2^j$, we are making use of two ranges of size $2^{j-1}$. One that starts from $i$ and goes until the middle element of the range : $i + (1<<(j - 1)) - 1$. Second that starts from next of the middle element : $i + (1<<(j - 1))$, till the end of the range which is $i + 2 \times (1 << (j - 1))$ which is just equal to $i + (1<<j)$. That's how this calculation works under the hood.

Now once $st$ is pre-calculated, you can use this to answer range minimum queries.

Let's say you need to find the min for the range $[L, R]$, you can do so by:
1. Find the size of the range = $R - L + 1$
2. Find the largest power of 2 that is lower or equal to this range = $log_2(R - L + 1)$. Let's call this $h$
3. Now use $h$ to calculate : $min(st[L][h], st[R - (1<<h) + 1][h]$

The final output will give you the min of the range.