笛卡尔树

定义与唯一性 ​

互异数组公理库数组Array以连续整数下标支持随机访问的有限序列结构。 (A[1..n]) 的最小笛卡尔树同时满足两种次序：中序遍历按下标 (1,\ldots,n) 出现，父节点的数组值小于孩子。全局最小值的下标只能做根；根左、右两段又分别服从同一规则，所以树形由递归唯一确定。

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

单调栈构造 ​

扫描到前缀末尾时，栈从底到顶恰是当前树的最右根叶路径，且堆键递增。处理新下标 (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])，下标 (l,r) 在笛卡尔树中的最低公共祖先恰是区间最小值位置。该祖先的子树中序覆盖两端，所以其下标位于区间内；堆序又使其值不大于子树中的所有后代。

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

验证与接口边界 ​

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

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

参考资料

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