Range Minimum Query <O(n), O(1)> approach (from tree to restricted RMQ)

Question

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.

Treadle

I'm not sure I understand what you mean by "how can this be achieved with my end result from the transform." Can you elaborate on what specifically is confusing you? – Audacious

@Audacious Okay, I will add it to the question. – Treadle

Where did you get this T array from? I don't see that described anywhere in the tutorial, so I'm not sure how to help. – Audacious

@Audacious "From RMQ to LCA". There's the code in that section. – Treadle

I guess I'm confused by your notation. You have two arrays in parallel for each array. What do the top and bottom numbers mean? – Audacious

@Audacious top is the position of the element, bottom is the element. I think it's more clear, but I'm wrong. Will remove it. Actually after I edited it, I find that copy and paste actually changed what I copied. Weird. Anyway, it's fixed. – Treadle

@RBarryYoung Yes, it was a mistake, and it's fixed. – Treadle

Answer 1

Here is my current understanding of what's confusing you:

1. In order to reduce RMQ to LCA, you need to convert the array into a tree and then do an Euler tour of that tree.
2. In order to do an Euler tour, you need to store the tree such that each node points at its children.
3. The reduction that is listed from RMQ to LCA has each node point to its parent, not its children.

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:

• Create an array of n nodes. Each node has a value field, a left child, and a right child.
• Initially, set the nth node to have a null left child, null right child, and the value of the nth element from the array.
• Iterate across the T array (where T[n] is the parent index of n) and do the following:
  • If T[n] = *, then the nth entry is the root. You can store this for later use.
  • Otherwise, if T[n] < n, then you know that node n must be a right child of its parent, which is stored at position T[n]. So set the T[n]th node's right child to be the nth node.
  • Otherwise, if T[n] > n, then you know that node n must be a left child of its parent, which is stored at position T[n]. So set the T[n]th node's left child to be the nth node.

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!

Audacious

Thanks! It did help, a lot! Thank you for taking so much time commenting and answering! – Treadle