问题标签 [cartesian-tree]

因此，我阅读了有关 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 的缩减部分中进行了介绍。这涉及到这棵树的欧拉之旅。但是，如何通过转换的最终结果来实现呢？我的方法不是线性的，所以在这种方法中应该被认为是不好的，线性方法是什么？

更新：让我感到困惑的一点

树的图片：

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

任何人都可以提供真实的例子来说明什么时候存储数据的最佳方式是陷阱？

我想了解在哪些情况下，treap 会比堆和树结构更好。

如果可能，请提供一些真实情况的例子。

我试图在这里和谷歌搜索搜索使用陷阱的案例，但没有找到任何东西。

谢谢你。

我知道如何在 O(n) 时间内将数组转换为笛卡尔树

1. http://en.wikipedia.org/wiki/Cartesian_tree#Efficient_construction和
2. http://community.topcoder.com/tc?module=Static&d1=tutorials&d2=lowestCommonAncestor#从 RMQ 到 LCA

但是，所需的内存量太高（常量），因为我需要至少将左右指针与笛卡尔树中的每个节点相关联。

任何人都可以将我与减少这些常数的工作联系起来（希望减少到 1）吗？

我在数据结构课程中进行了测试，其中一个问题是：

假设您有一个 n 大小的数组，该数组由 Range Minimum Query 维护，该查询给出了 o(1) 复杂度的数组中两个数字之间的最小值。当然，该数组是 o(n) 准备使用动态编程针对不同选项来回答 RMQ 的。问题是 - 如果我更改数组中的一个对象（数字），我将如何更改我所做的准备工作以便我仍然可以在 o(1) 中找到 RMQ，以及它需要什么复杂性。

答案不是在 o(n) 中创建一个新的 RMQ，它必须小于这个值。

这个问题不是作业，我只是想通过测试来理解。

提前致谢。

假设我有一个给定的数组 A。现在有多个形式的操作

和

打印数组 Ai..j。

例子 ，

我听说可以通过笛卡尔树来完成。所以我一直在这里阅读博客 但是我仍然不明白我们如何使用笛卡尔树来做到这一点，关键和价值应该是什么以及我们应该如何实现？

输入是一个数组(n*m 1<n,m< 1000)。我必须在 的每个子矩阵中找到最大元素size( a*b )。

我试图通过x一遍n-a+1又一y遍地迭代来做到这一点m-j+1。

• 2D segment treesor quad trees不够快，因为查询的数量很大。

• 我试图扩展sparse table，但由于空间不足而无法扩展。

• 我已经阅读了有关解决方案的信息，Cartesian trees但是由于我无法理解，因此需要一些代码。

请解释一个将通过预计算O(nm)及时或及时回答查询的解决方案。O(1)此外，输入数组是静态的。

注意：虽然我试过sparse table了，但它可能不正确，所以请随时发布解决方案。

我是一名Java编码员，所以实现Java或c/c++将是伟大的。

这也不是重复的，因为我已经搜索了很多关于它没有找到任何合适的东西。

我需要帮助才能从树中找到所有组合的可能性

我阅读了很多关于笛卡尔积的文档，尝试了很多东西，但它们似乎都不能正常工作......

这是我的树

这是我的预期结果：

当然，可以填充每个空数组... :)

谢谢你的帮助:)