笛卡尔树学习笔记

笛卡尔树

引入

是一种二叉树，每个节点由一个二元组 \((k,w)\) 形成。\(k\) 满足二叉搜索树的性质，\(w\) 满足堆的性质。

上面这棵笛卡尔树相当于把数组元素值当作键值 \(w\)，而把数组下标当作键值 \(k\)。显然可以发现，这棵树的键值 \(k\) 满足二叉搜索树的性质，而键值 \(w\) 满足小根堆的性质。

构建

于是我们执行这样一个过程，从下往上比较右链结点与当前结点 \(u\) 的 \(w\)，如果找到了一个右链上的结点 \(x\) 满足 \(x_w<u_w\)，就把 \(u\) 接到 \(x\) 的右儿子上，而 \(x\) 原本的右子树就变成 \(u\)​ 的左子树。

例题

Problem - 1506 (hdu.edu.cn)