笛卡尔树 学习笔记

碰到好多次了，系统的整理一下。

定义

笛卡尔树跟 Treap 的定义是一样的：

• 二叉树
• 每个节点有一个键值 $(k,w)$。
• $k$ 满足二叉搜索树的性质。
• $w$ 满足二叉堆的性质。

严格意义上讲，Treap 是 $w$ 随机的笛卡尔树。

通常我们可以对一个序列构建笛卡尔树：以下标为 $k$，以元素为 $w$。

这样构建的笛卡尔树的每一个子树都对应着序列的一个区间。

构建

由于对 $k$ 排序后，每次一定是在笛卡尔树的右链上插入一个新的元素。

因此我们可以利用单调栈维护右链。每当一个新节点找到一个位置插入后，把原来那个位置上的子树作为新节点的左儿子即可。

总时间复杂度 $\mathcal O(n)$。

【模板】P5854 【模板】笛卡尔树

const int N = 1e7 + 7;
int n, a[N], s[N], t, l[N], r[N];
ll L, R;

int main() {
	rd(n);
	for (int i = 1; i <= n; i++) {
		rd(a[i]);
		int k = t;
		while (k && a[s[k]] > a[i]) --k;
		if (k) r[s[k]] = i;
		if (k < t) l[i] = s[k+1];
		s[++k] = i, t = k;
	}
	for (int i = 1; i <= n; i++) L ^= 1ll * i * (l[i] + 1), R ^= 1ll * i * (r[i] + 1);
	print(L, ' '), print(R);
	return 0;
}

【例题】P1377 [TJOI2011]树的序

这题实际上是求以元素为 $w$、以下标为 $k$ 的笛卡尔树的先序遍历。

const int N = 1e5 + 7;
int n, a[N], s[N], t, l[N], r[N];
ll L, R;

void dfs(int x) {
	if (x) print(x, ' '), dfs(l[x]), dfs(r[x]);
}

int main() {
	rd(n);
	for (int i = 1, x; i <= n; i++) rd(x), a[x] = i;
	for (int i = 1; i <= n; i++) {
		int k = t;
		while (k && a[s[k]] > a[i]) --k;
		if (k) r[s[k]] = i;
		if (k < t) l[i] = s[k+1];
		s[++k] = i, t = k;
	}
	dfs(s[1]);
	return 0;
}

参考资料

• OI Wiki 笛卡尔树