10

因此，我阅读了有关 RMQ（范围最小查询）的 TopCoder 教程，我遇到了一个大问题。

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

（整个方法实际上使用了稀疏表（ST）算法中引入的方法，从 LCA 到 RMQ以及从 RMQ 到 LCA的缩减）

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

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

但这是我无法理解的。O(n) 方法需要一个数组 where |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.

树的图片：

数据中的笛卡尔树

Euler Tour 需要知道每个节点的子节点，就像 DFS（深度优先搜索）一样，而 T[n] 只有每个元素的根，而不是子节点。

4

1 回答 1

9

这是我目前对让您感到困惑的事情的理解：

  1. 为了将 RMQ 简化为 LCA，您需要将数组转换为树，然后对该树进行欧拉之旅。
  2. 为了进行欧拉之旅，您需要存储树，使每个节点都指向其子节点。
  3. 从 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) 时间内运行，因为每个节点只被处理一次。

完成此操作后，您就明确构建了所需的树结构并拥有指向根的指针。从那里开始，继续算法的其余部分应该相当简单。

希望这可以帮助！

于 2013-02-08T18:01:18.943 回答