笛卡尔树

在线性时间内将任何数组转换为笛卡尔树。

背景

笛卡尔树是一种派生数据结构。它是从底层数组派生出来的。更正式地说，数组的笛卡尔树 T 是一个由 A 的元素组成的最小二叉堆，其组织方式使得树的先序遍历产生原始数组。

要从底层数组构建笛卡尔树，我们遵循以下原则：

• 先序遍历必须产生数组元素
• 树应该是一个最小堆。也就是说，最小元素应该在根节点。
• 在进行先序遍历时，先获取父节点和左子节点，然后再获取右子节点。因此，最右边的节点将是最后获取的节点。

等等，但是为什么？

为什么笛卡尔树很重要？当解决 范围最小查询 问题时它们非常有用：给定一个数组的笛卡尔树，我们可以回答该数组上的任何RMQ。特别是，$RMQ_A(o, j) = LCA_T(A[i], A[j])$。也就是说，我们可以通过在笛卡尔树中进行最低公共祖先搜索来回答RMQ。更多信息请参阅这里。

实现细节

我们增量地构建笛卡尔树--按照数组中元素出现的顺序添加元素。要添加元素 X，我们从最右边的节点开始检查树的右脊。我们跟随父指针，直到我们找到一个在树中小于 X 的元素，称为 Y。然后我们修改树，将 X 作为 Y 的右子节点。我们还使 X 以下的其余右子树成为新节点的左子树。

通过将节点保存在栈中，可以从右至左高效地遍历树的右脊。这样，最右边的节点总是位于栈顶。

笛卡尔树同构

当两个数组的笛卡尔树，A 和 B，具有相同的形状时，会发生什么？我们如何有效地判断这一点？

简单来说，如果两个数组具有相同的笛卡尔树形状，那么在任意的范围内，两个数组中的最小值都出现在相同的索引处。这意味着，在构建两个数组的笛卡尔树时，Push 和 Pop 操作的序列是完全相同的。因此，要判断两个数组是否同构，我们可以简单地比较构建每个树所需的操作。

作为补充，当我们只对两个数组是否具有同构树感兴趣时，我们甚至不需要构建树。我们可以从 Push 和 Pop 操作的序列中创建一个位串。这个位串形成的数字称为 笛卡尔树编号。因此，按照这种方案，如果两个数组具有相同的笛卡尔树编号，则它们具有同构树。

进一步阅读

笛卡尔树应用于RMQ问题