Sparse Table for RMQ

A sparse table precomputes the minimum over every range of length $2^k$ for all starting positions. For each index $i$ and power $k$, store st[i][k] = min(tourDepth[i], ..., tourDepth[i + 2^k - 1]). To query $min(l, r)$, find the largest $k$ such that $2^k \leq r - l + 1$.

The answer is min(st[l][k], st[r - 2^k + 1][k]). These two ranges overlap but cover $[l, r]$. Preprocessing takes $O(n \log n)$, queries take $O(1)$.

Space complexity is $O(n \log n)$ for the data structures used.