笛卡尔树

引入

笛卡尔树是一种二叉树，每一个节点由一个键值二元组 $(k, w)$ 构成。要求 $k$ 满足二叉搜索树的性质，而 $w$ 满足堆的性质。如果笛卡尔树的 $k, w$ 键值确定，且 $k$ 互不相同， $w$ 也互不相同，那么这棵笛卡尔树的结构是唯一的。如下图：

（图源自维基百科）

上面这棵笛卡尔树相当于把数组元素值当作键值 $w$ ，而把数组下标当作键值 $k$ 。可以发现，这棵树的键值 $k$ 满足二叉搜索树的性质，而键值 $w$ 满足小根堆的性质。同时根据二叉搜索树的性质，可以发现这种特殊的笛卡尔树满足一棵子树内的下标是一个连续区间。

竞赛中使用笛卡尔树时，常用数组下标作为二元组的键值 $k$ 。

用栈构建笛卡尔树

过程

我们考虑将元素按下标顺序依次插入到当前的笛卡尔树中。那么每次我们插入的元素必然在这棵树的右链（右链：即从根节点一直往右子树走，经过的节点形成的链）的末端。于是我们执行这样一个过程，从下往上比较右链节点与当前节点 $u$ 的 $w$ ，如果找到了一个右链上的节点 $x$ 满足 $w_x

本页面最近更新：2024/7/30 18:20:55，更新历史
发现错误？想一起完善？在 GitHub 上编辑此页！
本页面贡献者：GavinZhengOI, sshwy, ouuan, ksyx, mgt, Enter-tainer, Ir1d, ouuan, StudyingFather, AngelKitty, HeRaNO, iamtwz, jimmyas, kenlig, littleyinhee, megakite, zhouyuyang2002
本页面的全部内容在 CC BY-SA 4.0 和 SATA 协议之条款下提供，附加条款亦可能应用