Enumerating all Binary Trees to build O(n)/O(1) RMQ
Difference between en8 and en9, changed 0 character(s)
[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?

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en9 English SecondThread 2019-11-24 21:14:02 0 (published)
en8 English SecondThread 2019-11-24 21:13:06 18 Tiny change: 'lockSize^2)$.\n\nBut' -> 'lockSize^2 * nCartesianTrees)$.\n\nBut'
en7 English SecondThread 2019-11-24 21:11:49 149
en6 English SecondThread 2019-11-24 21:08:55 1011
en5 English SecondThread 2019-11-24 20:49:19 8
en4 English SecondThread 2019-11-24 20:47:34 2 Tiny change: 'ilt with _O(n)_ memory (' -> 'ilt with __O(n)__ memory ('
en3 English SecondThread 2019-11-24 20:47:26 4 Tiny change: 'uilt with `O(n)` memory (O' -> 'uilt with _O(n)_ memory (O'
en2 English SecondThread 2019-11-24 20:45:24 3 Tiny change: 'uilt with O(n) memory (O' -> 'uilt with `O(n)` memory (O'
en1 English SecondThread 2019-11-24 20:44:50 161 Initial revision (saved to drafts)