笛卡尔树

l1ng21y12026 · 2025-11-25 19:58:57 · 算法·理论

笛卡尔树

笛卡尔树是一种二叉树，每个节点有键值 (k,w)。要求 k 满足二叉搜索树的性质，w 满足堆的性质。

• 二叉搜索树：x 左子树所有 k 比 k_x 小，x 右子树所有 k 比 k_x 大。
• 小根堆堆：w_x 比 w_{lson},w_{rson} 小。

常使用下标作为 k，值作为 w。构建出来的树即每次按照区间最大值分治得到的树。

存在 O(n) 建树方法。

下标从小到大遍历，根据二叉搜索树的性质，当前点应该加在最右边。称从当前根节点一直向右儿子遍历得到的路径为“右链”，我们先把当前点放在右链尾部。

接下来进行调整使其满足小根堆的性质，若 w_x<w_{fa}，将 fa 和其左子树一起变成 x 的左子树，x 变为父亲。

使用栈维护“右链”，每个点只会进出一次，故为 O(n)。

void build(){
    for(rg i=1;i<=n;i++){
        while(top>0&&a[st[top]]>a[i])ls[i]=st[top--];
        if(st[top]!=0)rs[st[top]]=i;
        st[++top]=i;
    }
}