笛卡尔树

形式陈述 ​

定义与唯一性 ​

设互异数组公理库数组Array以连续整数下标支持随机访问的有限序列结构。 $A[1..n]$ 的值取自一个全序公理库全序Total order · Linear order任意两个元素都可比较的偏序。集合。它的最小笛卡尔树同时满足两种次序：中序遍历按下标 $1,\dots ,n$ 出现，父节点的数组值小于孩子。全局最小值的下标只能做根；根左、右两段又分别服从同一规则，所以树形由递归唯一确定。

重复值会破坏“全局最小下标唯一”。若接口要求并列时返回较小下标，可把堆键统一改成 $(A[i],i)$ 的字典序；构造、RMQ 和验证都必须使用同一个 tie-breaking 规则。

单调栈构造 ​

扫描到前缀末尾时，栈从底到顶恰是当前树的最右根叶路径，且堆键递增。处理新下标 $i$ 时，连续弹出所有键大于它的栈顶；最后弹出的节点成为 $i$ 的左孩子，仍留在栈顶的节点成为 $i$ 的父亲，随后把 $i$ 入栈。

被弹出的节点原本处在最右路径上，且都位于新下标左侧。让整段弹出链挂到新节点左侧，既保留中序下标关系，也恢复父键小于子键的堆序。未被弹出的栈顶比新键小，又是离它最近的未闭合祖先，因此应成为父亲。

对 $A=(3,1,4,2)$，栈状态是

$$(3)\to (1)\to (1,4)\to (1,2).$$

读到 1 时弹出 3，故下标 1 成为根 2 的左孩子；读到最后的 2 时弹出值 4 对应的下标 3，让它成为新节点 4 的左孩子，而值 1 对应的下标 2 仍做父亲。最终根是下标 2，右孩子是下标 4，后者的左孩子是下标 3。

每个下标只入栈一次、出栈至多一次，所以所有 while 弹栈总计 $O(n)$，而非每轮最坏弹 $O(n)$ 后相乘。实现可输出 root、left、right、parent 四组下标；挂接新左孩子时要先解除它与旧父亲的右子关系，否则会在数组表示中留下两个父指针。

直觉

笛卡尔树把数组的两种秩序同时固定下来：中序位置保留原下标，堆序祖先记录区间里的较小值。于是一个区间的最小元素恰好是包住两端下标的最深祖先；单调栈公理库单调栈Monotonic stack通过弹出破坏单调性的元素，在线性总时间内维护尚未被更优后继支配的候选位置。则在从左到右扫描时只维护尚未确定右边界的祖先链。

例子与边界

RMQ 与 LCA ​

对区间 $[l,r]$，下标 $l,r$ 在笛卡尔树中的最低公共祖先恰是区间最小值位置。该祖先的子树中序覆盖两端，所以其下标位于区间内；堆序又使其值不大于子树中的所有后代。

若区间中另有更小节点，它会是覆盖 $l,r$ 的更高祖先，与“最低公共祖先”矛盾。因此静态 RMQ 可先把数组编成树，再归约为 LCA。上例查询 $[3,4]$ 时，两端节点的 LCA 是下标 4，对应值 2，正是该区间最小值。

验证与接口边界 ​

构造后的线性验证要同时检查中序遍历为 $1,\dots ,n$、每条父子边满足堆序，并确认每个非根节点恰有一个父亲。只检查值递增会漏掉下标错接，只检查中序又会接受不满足最小堆序的任意二叉树公理库二叉树Binary tree每个节点至多有两个有序子节点的根树。。

它不是按数组值搜索的 BST：中序键是固定下标，不能据此寻找某个数值。Treap 的中序是字典键、堆序是随机优先级，二者共享“双序唯一树”的形状定理，应用与概率语义不同。单点改值可能让一个节点跨越很长祖先链，静态线性构造也不自动提供廉价动态更新。

推论与应用

把静态数组线性构造成笛卡尔树后，RMQ 可归约到 LCA，并进一步使用 Euler tour 与简洁 RMQ 结构获得常数查询。相同的“双序”结构也出现在 Treap 中，但后者把字典键作为中序、随机优先级作为堆序，不能直接继承数组区间的语义。

参考资料

• Jean Vuillemin, “A Unifying Look at Data Structures,” 1980.
• Gabow, Bentley, Tarjan, STOC 1984.