Problem - Static Range Min

Given a static array of $n$ integers and $q$ queries, find the minimum in each queried range. You're solving the canonical Sparse Table problem.

With $q = 10^6$ queries, the $O(1)$ query time is needed. Compare:

• Naive: $O(nq)$ . Too slow
• Segment Tree: $O(n + q \log n)$
• Sparse Table: $O(n \log n + q)$ For $n = 10^5$ and $q = 10^6$:
• Segment Tree: ~$20 \cdot 10^6$ operations
• Sparse Table: ~$10^6$ operations (after preprocessing) Constraints: $n$ up to $10^5$, $q$ up to $10^6$.