According to Wikipedia, an RMQ can be built with $$$O(n)$$$ memory ($$$O(n)$$$ precomp) that can answer queries in $$$O(1)$$$. The idea is to divide the array into $$$log(n)/4$$$ blocks and then build an RMQ/sparse table normally on each of the blocks using $$$O(nBlocks*log(nBlocks))$$$ time and memory. In this case, $$$nBlocks$$$ is roughly $$$n/log(n)$$$ so the memory and time used to precomp everything is linear. By doing this, we can find the min of all completely covered blocks. That part sounds easy.

The hard part is dealing with the blocks that a query starts and ends in. Wikipedia says that I need to map each block to its corresponding Cartesian tree, and then I can precompute all the answers for every Cartesian tree. I see how, if I could do that, it would be easy to answer queries in $$$O(1)$$$. As I understand it, I could just store which index for a given Cartesian tree contains the relevant min for all pairs of queries within that subarray in $$$O(blockSize^2)$$$.

But how do I go about quickly (and hopefully cleanly) mapping a subarray to its corresponding Cartesian tree?