RMQ Solution

Implement Sparse Table for range minimum queries.

Implementation details:

• $K = \lfloor \log_2 n \rfloor + 1$ is the number of power-of-2 lengths needed
• The inner loop bound n - (1 << j) + 1 ensures we don't exceed array bounds
• Precomputed LOG array avoids expensive log calls Testing:
• Single element range
• Entire array range
• Random ranges
• Verify against brute force for small inputs For $10^6$ queries on $10^5$ elements, Sparse Table answers each query in $O(1)$ vs. $O(\log n)$ for a segment tree.

Time: $O(1)$. Space: $O(n \log n)$.