Enumerating all Binary Trees to build O(n)/O(1) RMQ

Правка en6, от SecondThread, 2019-11-24 21:08:55

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?

Теги range minimum query, 4-russians

История

 
 
 
 
Правки
 
 
  Rev. Язык Кто Когда Δ Комментарий
en9 Английский SecondThread 2019-11-24 21:14:02 0 (published)
en8 Английский SecondThread 2019-11-24 21:13:06 18 Tiny change: 'lockSize^2)$.\n\nBut' -> 'lockSize^2 * nCartesianTrees)$.\n\nBut'
en7 Английский SecondThread 2019-11-24 21:11:49 149
en6 Английский SecondThread 2019-11-24 21:08:55 1011
en5 Английский SecondThread 2019-11-24 20:49:19 8
en4 Английский SecondThread 2019-11-24 20:47:34 2 Tiny change: 'ilt with _O(n)_ memory (' -> 'ilt with __O(n)__ memory ('
en3 Английский SecondThread 2019-11-24 20:47:26 4 Tiny change: 'uilt with `O(n)` memory (O' -> 'uilt with _O(n)_ memory (O'
en2 Английский SecondThread 2019-11-24 20:45:24 3 Tiny change: 'uilt with O(n) memory (O' -> 'uilt with `O(n)` memory (O'
en1 Английский SecondThread 2019-11-24 20:44:50 161 Initial revision (saved to drafts)