笛卡儿树

笛卡儿树是一种特殊的堆，它的重要应用之一是实现RMQ问题向LCA问题的转化。

笛卡儿树根据一个数列构造，其根结点是长为n的数列A中的最小值A的下标i，左右

孩子分别是由数列A[1...i-1]和A[i+1...n]构造的笛卡儿树。下面的内容里，我们说笛卡

儿树某结点的值，指的是其存储的下标在原数组里对应的值。

由于笛卡儿树的这一特性，不难发现求原数列A的某一段最小值，相当于求这一段的

左右两端在笛卡儿树上所对应结点的最近公共祖先。

这里有一个定理：

数组A的Cartesian树记为C(A)，则RMQ(A,i,j)=LCA(C(A),i,j).

证明略。

现在急待解决的问题是笛卡儿树的建立方法。笛卡儿树不一定是完全二叉树，所以与

堆的操作有些不同。由于笛卡儿树的特性，对其进行中序遍历一定会得到原数列，也

就是说，可以把笛卡儿树看作是将原数列中的最小值“提升”到最高处，再将左右两部

分的最小值分别“提升”到次高处…，最终形成一棵二叉树。所以我们由A[1]开始逐个

将数列里的数加入笛卡儿树内，新加入的结点一定在树的最右路径的最右端(没有右

孩子)。当加入A时我们在已有的笛卡儿树上找到最右路径上找到大于A最小值，将

它的父结点作为新结点的父结点，它则作为新结点的左孩子。若根结点大于A则整个

树作为新结点的左孩子，若最右路径上没有大于A的结点，则A加入最右路径的最

右下端。

由于每个结点最多进入和退出最右路径各一次，因此均摊时间复杂度为θ(n)。