范围最小查询<O(n)，O(1)>方法(从树到受限RMQ)

Question

所以，我读了关于RMQ (范围最小查询)的this TopCoder教程，我有一个很大的问题。

在他介绍 approach的部分，到目前为止我能理解的是：

(整个方法实际上使用了Sparse Table (ST) Algorithm、Reduction from LCA to RMQ和from RMQ to LCA中引入的方法)

给定一个数组AN，我们需要将其转换为笛卡尔树，从而使RMQ问题成为LCA (最低公共祖先)问题。稍后，我们可以得到数组A的简化版本，并使其成为一个受限的RMQ问题。

所以它基本上是两个变换。因此，RMQ到LCA的第一部分很简单。通过使用堆栈，我们可以在O(n)时间内进行转换，得到一个数组TN，其中Ti是元素i的父元素。这棵树就完成了。

但这是我不能理解的。O(n)方法需要一个包含|A[i] - A[i-1]| = 1的数组，本教程的Reduction from LCA to 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.

一张树的图片：

​

​

Euler Tour需要知道每个节点的子节点，就像DFS (深度优先搜索)一样，而Tn只有每个元素的根，而不是子元素。

Answer 1

这是我目前对什么让你感到困惑的理解：

1. 为了将RMQ减少到LCA，您需要将数组转换为树，然后对该树执行欧拉遍历。
2. 要执行Euler遍历，您需要存储树，以便每个节点指向其子代。
3. 列出的从RMQ到LCA的缩减使每个节点指向其父代，而不是其子代。

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

• 创建n个节点的数组。每个节点都有一个值字段、一个左子节点和一个右child.
• Initially，将第n个节点设置为具有空的左子节点、空的右子节点以及跨T数组的array.
• Iterate的第n个元素的值(其中Tn是n的父索引)，并执行以下操作：
  • 如果Tn = *，则第n个条目是根。如果Tn < n，那么您知道节点n必须是其父节点的右子节点，该父节点存储在位置Tn处。如果Tn
  • Otherwise，。因此，如果Tn > n，则将第n个节点的右子节点设置为第n个node.
  • Otherwise，，那么您就知道节点n必须是其父节点的左子节点，父节点存储在位置Tn。因此，将第n个节点的左子节点设置为第n个node.

​

这在O(n)时间内运行，因为每个节点恰好被处理一次。

一旦完成此操作，您就已经显式地构造了所需的树结构，并拥有了指向根的指针。从那里开始，继续算法的其余部分应该是相当简单的。

希望这能有所帮助！