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

问题描述

所以，我读<一href="http://community.top$c$cr.com/tc?module=Static&d1=tutorials&d2=lowestCommonAncestor#Sparse_Table_%28ST%29_algorithm">this在RMQ（范围最小查询），我顶codeR教程有一个大的问题。

So, I read this TopCoder tutorial on RMQ (Range Minimum Query), and I got a big question.

在那里，他引进了<一节href="http://community.top$c$cr.com/tc?module=Static&d1=tutorials&d2=lowestCommonAncestor#A%20O%28N%29,%20O%281%29%20algorithm%20for%20the%20restricted%20RMQ"><为O（n），O（1）>办法，有什么我能理解到现在为止是这样的：

On the section where he introduced the < O(n), O(1) > approach, what I can understand until now is this:

（整个逼近实际使用的方法在<一推出href="http://community.top$c$cr.com/tc?module=Static&d1=tutorials&d2=lowestCommonAncestor#Sparse_Table_%28ST%29_algorithm">Sparse表（ST）算法，<一个href="http://community.top$c$cr.com/tc?module=Static&d1=tutorials&d2=lowestCommonAncestor#Reduction%20from%20LCA%20to%20RMQ">Reduction从LCA到RMQ 和<一href="http://community.top$c$cr.com/tc?module=Static&d1=tutorials&d2=lowestCommonAncestor#From%20RMQ%20to%20LCA">from 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 [1] - A [I-1] | = 1 ，并且该数组是<一推出href="http://community.top$c$cr.com/tc?module=Static&d1=tutorials&d2=lowestCommonAncestor#Reduction%20from%20LCA%20to%20RMQ">Reduction从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?

更新：这让我困惑的一点

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.

树的图片：

一个欧拉游需要知道每个节点的孩子，就像一个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. 在为了做一个欧拉，你需要存储树等，在其子女的每个节点百分点。
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]＆LT; n，那么你知道该节点n必须为其父，其存储在位置T [N]的右孩子。因此，设置T [N]个节点的右子是第n个节点。
  • 否则，如果T [N]> N，那么你就知道该节点n必须为其父，其存储在位置T [N]的左子。因此，设置T [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屋！