笛卡尔树 | Codeboy's Blog

形式陈述

定义与唯一性

对非空输入，设互异数组 $A[1..n]$ 的值取自一个全序集合。它的最小笛卡尔树同时满足两种次序：中序遍历按下标 $1,\ldots,n$ 出现，父节点的数组值小于孩子。全局最小值的下标只能做根；根左、右两段又分别服从同一规则，所以树形由递归唯一确定。空数组对应空二叉树，没有根或非空 RMQ 查询。

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

单调栈构造

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

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

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

(3)\rightarrow(1)\rightarrow(1,4)\rightarrow(1,2).

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

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

直觉

笛卡尔树把数组的两种秩序同时固定下来：中序位置保留原下标，堆序祖先记录区间里的较小值。于是一个区间的最小元素恰好是包住两端下标的最深祖先；单调栈则在从左到右扫描时只维护尚未确定右边界的祖先链。

例子与边界

RMQ 与 LCA

对区间 $[l,r]$ ，记两端节点的最近公共祖先为 $k$ 。若 $k<l$ ，两端都在它的右子树中，便能在该子树内找到更低的公共祖先； $k>r$ 同理。因此 $l\le k\le r$ 。节点 $k$ 的子树在中序中是一段连续区间，包含两端，也就包含整个 $[l,r]$ ；堆序保证 $A[k]$ 不大于区间内任何值。

因此静态 RMQ 可先把数组编成树，再归约为 LCA。上例查询 $[3,4]$ 时，两端节点的 LCA 是下标 4，对应值 2，正是该区间最小值。

验证与接口边界

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

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

推论与应用

把静态数组线性构造成笛卡尔树后，RMQ 可归约到 LCA，并进一步使用 Euler tour 与简洁 RMQ 结构获得常数查询。

Powersort把原段边界的power序列编成最小笛卡尔树，并在弹栈时直接执行已闭合子树的归并。power在不同子树可以重复，但有序中点的首分歧位保证每个连续边界范围的最小值唯一，因此这里仍有唯一递归根；不能把这个特殊性质误当成任意重复数组的结论。

参考资料

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

形式陈述 ​

定义与唯一性 ​

单调栈构造 ​

RMQ 与 LCA ​

验证与接口边界 ​

反向链接

形式陈述

定义与唯一性

单调栈构造

RMQ 与 LCA

验证与接口边界