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

Question

所以,我在RMQ(范围最小查询)上阅读了这个 TopCoder教程,我有一个很大的问题.

在他介绍这种方法的部分,到目前为止我能理解的是:

(整个方法实际上使用稀疏表(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.

树的图片:

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

Answer 1

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

1. 为了将RMQ降低到LCA,您需要将数组转换为树,然后对该树进行Euler巡视.
2. 要进行Euler巡视,您需要存储树,以便每个节点指向其子节点.
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)中运行,因为每个节点只处理一次.

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

希望这可以帮助!