笛卡尔树

摘要

本文介绍一种不太常用,但是与大家熟知的平衡树与堆密切相关的数据结构——笛卡尔树。

笛卡尔树是一种二叉树,每一个结点由一个键值二元组 构成。要求 满足二叉搜索树的性质,而 满足堆的性质。一个有趣的事实是,如果笛卡尔树的 键值确定,且 互不相同, 互不相同,那么这个笛卡尔树的结构是唯一的。上图:

eg

上面这棵笛卡尔树相当于把数组元素值当作键值 ,而把数组下标当作键值 。显然可以发现,这棵树的键值 满足二叉搜索树的性质,而键值 满足小根堆的性质。其实图中的笛卡尔树是一种特殊的情况,因为二元组的键值 恰好对应数组下标,这种特殊的笛卡尔树有一个性质,就是一棵子树内的下标是连续的一个区间(这样才能满足二叉搜索树的性质)。更一般的情况则是任意二元组构建的笛卡尔树。

构建

既然笛卡尔树有具有两种不同结构的性质,那么就有两种构建方法。其中一种的复杂度是 ,另一种是

栈构建

我们考虑将元素按照键值 排序。然后一个一个插入到当前的笛卡尔树中。那么每次我们插入的元素必然在这个树的右链(右链:即从根结点一直往右子树走,经过的结点形成的链)的末端。于是我们执行这样一个过程,从下往上比较右链结点与当前结点 ,如果找到了一个右链上的结点 满足 ,就把 接到 x 的右儿子上,而 x 原本的右子树就变成 u 的左子树。

具体不解释,我们直接上图。图中红色框框部分就是我们始终维护的右链:

build

显然每个数最多进出右链一次(或者说每个点在右链中存在的是一段连续的时间)。这个过程我们可以用栈维护,栈中维护当前笛卡尔树的右链上的结点。一个点不在右链上了就把它弹掉。这样每个点最多进出一次,复杂度

另一种构建

还有一种构建方式与之对应(这是我自己 YY 的)。我们按照 排序,始终维护堆的结构。这样插入一个结点,相当于添加一个叶子结点。于是我们像平衡树那样插入就行了。这样每一次插入的复杂度是 的,因此总复杂度是 的。

笛卡尔树与 Treap

谈到笛卡尔树,很容易让人想到一种家喻户晓的结构——Treap。没错,Treap 是笛卡尔树的一种,只不过 w 的值完全随机。Treap 也有线性的构建算法,如果提前将元素排好序,显然可以使用上述单调栈算法完成构建过程,只不过很少会这么用。

例题

HDU 1506 最大子矩形

题目大意:n 个位置,每个位置上的高度是 ,求最大子矩阵。举一个例子,如下图

eg

阴影部分就是图中的最大子矩阵。

这道题你可 DP,可单调栈,但你万万没想到的是它也可以笛卡尔树!具体地,我们把下标作为键值 作为键值 满足小根堆性质,构建一棵 的笛卡尔树。

这样我们枚举每个结点 ,把 (即结点 u 的高度键值 )作为最大子矩阵的高度。由于我们建立的笛卡尔树满足小根堆性质,因此 的子树内的结点的高度都大于等于 。而我们又知道 子树内的下标是一段连续的区间。于是我们只需要知道子树内的下标最小值和最大值即可,换言之,就是 子树内的左链和右链末端的结点的下标键值。我们对每个点这样求,最后取面积最大值即可。显然这个可以一次 DFS 完成,因此复杂度仍是 的。

参考资料

维基百科 - 笛卡尔树


  转载请注明: Sshwy's Blog 笛卡尔树

 上一篇
Tewelvefold way Tewelvefold way
摘要 今天我们来探讨一道综合计数题。 问题描述 n个有标号/无标号的球分给m个有标号/无标号的盒子,盒子有三种限制: A. 无限制B. 每个盒子至少有一个球C. 每个盒子至多一个球 共12种问题。问方案数。(所有球都要放) 为了方便,将
2019.07.20 Sshwy
下一篇 
Stern-Brocot 树与 Farey 序列 Stern-Brocot 树与 Farey 序列
摘要 Stern-Brocot树是一种维护分数的优雅的数据结构。它分别由Moritz Stern在1858年和Achille Brocot 在1861年发现这个结构。 概述Stern-Borcot 树从两个简单的分数开始: \frac{
2019.07.17
  目录