Space Optimization

Standard sparse table uses $O(n \log n)$ space. Can we do better? For problems where $n$ is large but queries need only a few levels, you can:

$1.$ Compute on-demand: Only compute levels you need. For small ranges, level 0-3 might suffice.

$2.$ Block decomposition + Sparse Table: Divide array into $\sqrt{n}$ blocks. Build sparse table only on block representatives.

$3.$ Fischer-Heun structure: $O(n)$ space, $O(1)$ query for RMQ (theoretically optimal but complex). For most competitive programming, the $O(n \log n)$ space is acceptable. These optimizations are for extreme cases.