标签: cartesian-tree

任何人都可以提供真正的例子,说明何时存储数据的最佳方式是什么？

我想了解哪种情况下treap会比堆和树结构更好.

如果可能的话,请提供一些实际情况的例子.

我试图在这里搜索使用treaps的情况,并通过谷歌搜索,但没有找到任何东西.

谢谢.

所以,我在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 …