范围最小查询方法（从一棵树到受限制的RMQ）(Range Minimum Query <O>

所以，我读了这对RMQ（范围最小查询）TopCoder的教程中，我得到了一个很大的问题。

在那里他介绍了该部分的做法，有什么我能理解到现在为止是这样的：

（整个逼近实际使用中所介绍的方法稀疏表（ST）算法，从LCA还原成RMQ ，并从RMQ到LCA ）

给定阵列的[N]，我们需要将其变换到笛卡尔树，从而使一个RMQ问题LCA（最低共同祖先）的问题。后来，我们可以得到数组A的简化版本，并使它成为一个受限制的RMQ问题。

因此，它基本上有两种变换。所以第一RMQ到LCA部分是简单的。通过使用堆栈，我们可以在O（n）的时间变换，从而产生一个阵列T [N]，其中T [i]为i的元素的父。和树完成。

但这里是我无法理解。的O（n）的方法需要一个数组，其中|A[i] - A[i-1]| = 1 |A[i] - A[i-1]| = 1 ，并且阵列在引入从LCA还原成RMQ教程的部分。涉及此树的欧拉。但是，这怎么能与来自变换我的最终结果能实现吗？我给它的做法是不是线性的，所以应该在这种方法被认为是不好的，这将是这种线性的方法呢？

UPDATE：这让我困惑的点

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]只有每个元素的根，而不是孩子。

这是我目前什么迷惑你的理解：

为了减少对RMQ LCA，您需要将数组转换成一棵树，然后做树的欧拉。
为了做一个欧拉，你需要将树存储，使得在其子女的每个节点分。
是从RMQ所列LCA的减少具有每个节点指向其父，而不是它的孩子。

如果是这样的话，你的顾虑是完全有道理的，但有一个简单的方法来解决这个问题。特别是，一旦你把所有的父指针数组，你可以将其转换为树，其中每个节点指向其子O（n）的时间。我们的想法是以下几点：

创建n个节点的数组。每个节点都有一个值字段，左孩子和右孩子。
最初，设置第n个节点有一个空左子，空右子，和从阵列的第n个元素的值。
跨越第t阵列（其中，T [n]是n的父索引）迭代，并执行以下操作：
- 如果T [N] = *，则第n个条目是根。您可以存储此供以后使用。
- 否则，如果T [N] <n，那么你知道，节点n必须是其母公司，其存储在位置T [N]的右孩子。所以设置T [N]个节点的右孩子是第n个节点。
- 否则，如果T [N]> N，那么你知道，节点n必须是其母公司，其存储在位置T [N]的左子。所以设置T [N]个节点的左子是第n个节点。

这个运行时间为O（n），因为每个节点被处理一次。

一旦做到这一点，你已经明确构造，你需要和有一个指向根树结构。从那里，它应该是相当简单的算法的其余部分进行。

希望这可以帮助！