范围最小查询< O（n），O（1）>方法（从树到受限RMQ） [英] Range Minimum Query <O(n), O(1)> approach (from tree to restricted RMQ)

问题描述

所以，我读了此关于RMQ（范围最小查询）的TopCoder教程，我遇到了一个大问题。

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:

（整个方法实际上使用了稀疏表（ST）算法， R从LCA到RMQ ，并且从RMQ到LCA ）

(The whole approach actually uses methodology introduced in Sparse Table (ST) Algorithm, Reduction from LCA to RMQ, and from RMQ to LCA)

给定数组A [N]，我们需要将其转换为笛卡尔树，从而使RMQ问题LCA（最低公共祖先）问题。稍后，我们可以获得数组A的简化版本，并将其作为受限的RMQ问题。

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.

因此，它基本上是两个转换。因此，第一个RMQ到LCA的部分很简单。通过使用堆栈，我们可以在O（n）时间内进行转换，从而得到一个数组T [N]，其中T [i]是元素i的父元素。树就完成了。

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.

但是，这是我不明白的地方。 O（n）方法需要一个数组，其中 | A [i]-A [i-1] | = 1 ，并且在从LCA减少到RMQ 部分。这涉及到这棵树的欧拉之旅。但是如何用转换的最终结果来实现呢？我的方法不是线性的，因此在这种方法中应该认为它是不好的，对此，线性方法是什么？

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?

更新：这让我感到困惑

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.

树的图片：

欧拉之旅需要知道每个节点的子节点，就像DFS（深度优先搜索）一样，而T [n]仅具有每个元素的根节点，而不是子节点。

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:

1. 为了减少RMQ到LCA，您需要转换


2. 为了进行欧拉遍历，您需要存储树使得每个节点都指向其子节点。 / li>
   
3. 从RMQ到LCA列出的减少量每个节点都指向其父节点，而不是其子节点。

在这种情况下，您的担心是完全合理的，但是有一种简单的方法可以解决此问题。具体来说，一旦有了所有父指针的数组，就可以将其转换为树，其中每个节点在O（n）时间内指向其子节点。这个想法如下：

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:

• 创建n个节点的数组。每个节点都有一个值字段，一个左子节点和一个右子节点。


• 最初，将第n个节点设置为具有一个空的左子节点，一个空的右子节点以及第n个节点的值。


• 遍历T数组（其中T [n]是n的父索引）并执行以下操作：
  
  
  
  • 如果T [n] = *，则第n个条目是根。您可以将其存储以供以后使用。
  
  
  • 否则，如果T [n]< n，那么您知道节点n必须是其父节点的右子节点，并存储在位置T [n]。因此，将第T [n]个节点的右子节点设置为第n个节点。
  
  
  • 否则，如果T [n]> n，则您知道节点n必须是第n个节点的左子节点。它的父对象存储在位置T [n]。因此，将第[n]个节点的左子节点设置为第n个节点。
  
  
  • 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.

    此操作在时间O（n）内运行，因为每个节点只被处理一次。

    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.

    希望这会有所帮助！

    这篇关于范围最小查询&lt; O（n），O（1）&gt;方法（从树到受限RMQ）的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！