Intro

You have a static array (no updates). You need to answer many range minimum queries: "what's the minimum element from index $l$ to $r$?" Segment trees give $O(\log n)$ per query.

Can we do better? Sparse Tables achieve $O(1)$ per query after $O(n \log n)$ preprocessing.

Here's the trick: for idempotent operations like $\min$ and $\max$, overlapping ranges don't affect the answer.

$\min(a, b, c) = \min(\min(a, b), \min(b, c))$ Even though $b$ appears twice, the result is correct.

Sparse Tables exploit this by precomputing answers for ranges of power-of-2 lengths, then combining two overlapping ranges to answer any query. In this section, I'll teach you this powerful technique and when to apply it.