范围最小查询<O(n)，O(1)>方法(从树到受限 RMQ) [英] Range Minimum Query &lt;O(n), O(1)&gt; approach (from tree to restricted RMQ)

问题描述

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

So, I read this TopCoder tutorial on RMQ (Range Minimum Query), and I got a big question.

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

On the section where he introduced the approach, what I can understand until now is this:

(整个方法实际上使用了稀疏表 (ST) 算法，从 LCA 减少到 RMQ，以及 从 RMQ 到 LCA)

(The whole approach actually uses methodology introduced in Sparse Table (ST) Algorithm, Reduction from LCA to RMQ, and from RMQ to LCA)

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

Given an array A[N], we need to transform it to a Cartesian Tree, thus making a RMQ problem a LCA (Lowest Common Ancestor) problem. Later, we can get a simplified version of the array A, and make it a restricted RMQ problem.

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

So it's basically two transforms. So the first RMQ to LCA part is simple. By using a stack, we can make the transform in O(n) time, resulting an array T[N] where T[i] is the element i's parent. And the tree is completed.

但这是我无法理解的.O(n) 方法需要一个数组，其中 |A[i] - A[i-1]|= 1，该数组在 从 LCA 减少到 RMQ 部分教程.这涉及到这棵树的欧拉之旅.但是，如何通过转换的最终结果来实现这一点?我的方法不是线性的，所以在这种方法中应该被认为是不好的，对此的线性方法是什么?

But here's what I can't understand. The O(n) approach needs an array where |A[i] - A[i-1]| = 1, and that array is introduced in Reduction from LCA to RMQ section of the tutorial. That involves a Euler Tour of this tree. But how can this be achieved with my end result from the transform? My approach to it is not linear, so it should be considered bad in this approach, what would be the linear approach for this?

更新:让我困惑的点

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

A Euler Tour needs to know each node's child, just like a DFS (Depth-First Search) while T[n] have only each element's root, not child.

推荐答案

以下是我目前对困扰您的理解:

Here is my current understanding of what's confusing you:

1. 为了将 RMQ 简化为 LCA，您需要将数组转换为一棵树，然后对该树进行欧拉之旅.
2. 为了进行欧拉之旅，您需要存储树，使每个节点都指向其子节点.
3. 从 RMQ 到 LCA 列出的归约使每个节点都指向其父节点，而不是其子节点.

如果是这种情况，您的担忧是完全有道理的，但有一种简单的方法可以解决此问题.具体来说，一旦您拥有所有父指针的数组，您就可以将其转换为一棵树，其中每个节点都在 O(n) 时间内指向其子节点.思路如下:

If this is the case, your concerns are totally justified, but there's an easy way to fix this. Specifically, once you have the array of all the parent pointers, you can convert it to a tree where each node points to its children in O(n) time. The idea is the following:

• 创建一个包含 n 个节点的数组.每个节点都有一个值字段、一个左孩子和一个右孩子.
• 最初，设置第 n 个节点的左子节点为 null，右子节点为 null，以及数组中第 n 个元素的值.
• 遍历 T 数组(其中 T[n] 是 n 的父索引)并执行以下操作:
  • 如果 T[n] = *，则第 n 个条目是根.您可以将其存储以备后用.
  • 否则，如果 T[n]
  • 否则，如果 T[n] > n，则您知道节点 n 必须是其父节点的左子节点，该节点存储在位置 T[n] 处.因此将第 T[n] 个节点的左子节点设置为第 n 个节点.

  这在时间 O(n) 中运行，因为每个节点只被处理一次.

  This runs in time O(n), since each node is processed exactly once.

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

  Once this is done, you've explicitly constructed the tree structure that you need and have a pointer to the root. From there, it should be reasonably straightforward to proceed with the rest of the algorithm.

  希望这有帮助！

  这篇关于范围最小查询<O(n)，O(1)>方法(从树到受限 RMQ)的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！