[According to Wikipedia](https://en.wikipedia.org/wiki/Range_minimum_query), an RMQ can be built with $O(n)$ memory and time 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 * nCartesianTrees)$.↵
↵
But how do I go about quickly (and hopefully cleanly) mapping a subarray to its corresponding Cartesian tree?↵
↵
Side question: Are there even performance gains to be made here, or am I just wasting my time trying to get rid of this log factor?
↵
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 * nCartesianTrees)$.↵
↵
But how do I go about quickly (and hopefully cleanly) mapping a subarray to its corresponding Cartesian tree?↵
↵
Side question: Are there even performance gains to be made here, or am I just wasting my time trying to get rid of this log factor?
