So, I read this TopCoder tutorial on RMQ (Range Minimum Query), and I got a big question.
On the section where he introduced the approach, what I can understand until now is this:
(The whole approach actually uses methodology introduced in Sparse Table (ST) Algorithm, Reduction from LCA to RMQ, and from RMQ to LCA)
Given an array A[N], we need to transform it to a Cartesian Tree, thus making a RMQ problem a LCA (Lowest Common Ancestor) problem. Later, we can get a simplified version of the array A, and make it a restricted RMQ problem.
So it's basically two transforms. So the first RMQ to LCA part is simple. By using a stack, we can make the transform in O(n) time, resulting an array T[N] where T[i] is the element i's parent. And the tree is completed.
But here's what I can't understand. The O(n) approach needs an array where |A[i] - A[i-1]| = 1
, and that array is introduced in Reduction from LCA to RMQ section of the tutorial. That involves a Euler Tour of this tree. But how can this be achieved with my end result from the transform? My approach to it is not linear, so it should be considered bad in this approach, what would be the linear approach for this?
UPDATE: The point that confuse me
Here's the array A[]:
n : 0 1 2 3 4 5 6 7 8 9
A[n]: 2 4 3 1 6 7 8 9 1 7
Here's the array T[]:
n : 0 1 2 3 4 5 6 7 8 9
T[n]: 3 2 0 * 8 4 5 6 3 8 // * denotes -1, which is the root of the tree
//Above is from RMQ to LCA, it's from LCA to RMQ part that confuses me, more below.
A picture of the tree:
A Euler Tour needs to know each node's child, just like a DFS (Depth-First Search) while T[n] have only each element's root, not child.
Here is my current understanding of what's confusing you:
If this is the case, your concerns are totally justified, but there's an easy way to fix this. Specifically, once you have the array of all the parent pointers, you can convert it to a tree where each node points to its children in O(n) time. The idea is the following:
This runs in time O(n), since each node is processed exactly once.
Once this is done, you've explicitly constructed the tree structure that you need and have a pointer to the root. From there, it should be reasonably straightforward to proceed with the rest of the algorithm.
Hope this helps!