所以，我读了关于rmq（range minimum query）的topcoder教程，我得到了一个大问题。
在他介绍this的那一节中，我现在能理解的是：
（整个方法实际上使用了 approach、Sparse Table (ST) Algorithm和Reduction from LCA to RMQ中介绍的方法）
给定一个数组a[n]，我们需要将其转换为笛卡尔树，从而使rmq问题成为lca（最低公共祖先）问题。稍后，我们可以得到数组a的一个简化版本，并使其成为一个受限rmq问题。
所以基本上是两个转变。因此，从rmq到lca的第一部分很简单。通过使用堆栈，我们可以在o（n）时间内进行转换，得到一个数组t[n]，其中t[i]是元素i的父元素。树也完成了。
但这是我不能理解的。o（n）方法需要一个|A[i] - A[i-1]| = 1的数组，该数组将在本教程的from RMQ to LCA部分介绍。这涉及到一个欧拉游览这棵树。但是，如何才能实现这一点与我的最终结果从转变？我的方法不是线性的，所以在这个方法中应该被认为是不好的，线性的方法是什么？
更新：让我困惑的一点
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.
树的图片：
euler巡更需要知道每个节点的子节点，就像dfs（深度优先搜索）一样，而t[n]只有每个元素的根节点，而不是子节点。
最佳答案
以下是我目前对你困惑的理解：
为了将rmq减少到lca，需要将数组转换为树，然后对树执行euler遍历。
为了执行euler漫游，需要存储树，使每个节点都指向其子节点。
从rmq到lca列出的缩减有每个节点指向其父节点，而不是其子节点。
如果是这样的话，你的担心是完全合理的，但有一个简单的方法来解决这个问题。特别是，一旦拥有所有父指针的数组，就可以将其转换为一棵树，其中每个节点在o（n）时间内指向其子节点。想法如下：
创建一个n个节点的数组。每个节点都有一个值字段、一个左子节点和一个右子节点。
最初，将第n个节点设置为具有空的左子节点、空的右子节点以及数组中第n个元素的值。
遍历t数组（其中t[n]是n的父索引）并执行以下操作：
如果t[n]=*，则第n个条目是根。你可以把这个储存起来以后再用。
否则，如果t[n]否则，如果t[n]>n，则知道节点n必须是其父节点的左子节点，该子节点存储在位置t[n]处。因此，将第t[n]个节点的左子节点设置为第n个节点。
这在时间o（n）中运行，因为每个节点只处理一次。
完成后，您将显式地构造所需的树结构，并拥有指向根的指针。从这里开始，继续算法的其余部分应该相当简单。
希望这有帮助！