所以，我读这
TopCoder的教程RMQ（范围最小查询），和我有一个很大的问题。

在他介绍该方法的部分中，到目前为止，我仍然可以理解：

（整个方法实际上使用的是稀疏表（ST）算法中引入的方法，即从LCA还原为RMQ以及从RMQ
还原为LCA）

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

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

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

更新：这一点让我感到困惑

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（深度优先搜索）一样，Euler Tour需要知道每个节点的子节点，而T [n]仅具有每个元素的根，而不是子节点。