笛卡尔树

时间：2019-07-19 00:51:42 阅读：89 评论：0 收藏：0 [点我收藏+]

笛卡尔树是一种特定的二叉树数据结构，可由数列构造，在范围最值查询、范围top k查询（range top k queries）等问题上有广泛应用。它具有堆的有序性，中序遍历可以输出原数列。笛卡尔树结构由Vuillmin(1980)^[1]在解决范围搜索的几何数据结构问题时提出。从数列中构造一棵笛卡尔树可以线性时间完成，需要采用基于栈的算法来找到在该数列中的所有最近小数。

定义

无相同元素的数列构造出的笛卡尔树具有下列性质：

结点一一对应于数列元素。即数列中的每个元素都对应于树中某个唯一结点，树结点也对应于数列中的某个唯一元素
中序遍历（in-order traverse）笛卡尔树即可得到原数列。即任意树结点的左子树结点所对应的数列元素下标比该结点所对应元素的下标小，右子树结点所对应数列元素下标比该结点所对应元素下标大。
树结构存在堆序性质，即任意树结点所对应数值大／小于其左、右子树内任意结点对应数值

根据堆序性质，笛卡尔树根结点为数列中的最大／小值，树本身也可以通过这一性质递归地定义：根结点为序列的最大／小值，左、右子树则对应于左右两个子序列，其结点同样为两个子序列的最大/小值。因此，上述三条性质唯一地定义了笛卡尔树。若数列中存在重复值，则可用其它排序原则为数列中相同元素排定序列，例如以下标较小的数为较小，便能为含重复值的数列构造笛卡尔树。

笛卡尔树应用

范围最值查询与最低公共祖先

三边范围查询问题

笛卡尔树可以有效地处理范围最值查询（range minimum queries），通过将定义在数列上的RMQ问题转化为定义在树结构上的最低公共祖先（lowest common ancestor）问题。数列以线性时间构造出笛卡尔树，笛卡尔树则能以常数时间处理最低公共祖先查询，因此在线性时间的预处理后，范围最值查询能以常数时间完成。

Bender & Farach-Colton (2000)^[2]则提出了RMQ与LCA问题的新联系，他们通过不基于树的算法处理RMQ问题从而有效地解决LCA问题。其使用欧拉路径的技巧将树结构转化为数列，此数列具有特定性质（相邻数值代表树中的相邻顶点，即在树中高度差为1的顶点），利用这一性质RMQ问题可以很高效地得到解决。通常的数列则不具备此性质，为了将一般的数列转化为具有上述性质的数列，需要应用到笛卡尔树，具体过程为在普通数列上构造笛卡尔树，在笛卡尔树上使用欧拉路径转化的方法将树转化为具有上述性质的新数列。

范围最值查询问题也可以解释为二维范围查询问题，或者三边范围查询问题（three sided range queries），笛卡尔平面上的有限点集可以用来构造笛卡尔树，首先将这些点按照x取值排序，然后将y值作为数列中元素的值，以此数列建立笛卡尔树。若 S 为有限点集中满足 $技术分享图片$

笛卡尔树同样可以应用于以常数时间查询超度量空间内点对的距离。超度量空间内距离的定义与最宽路径问题中的权重相同。从最小生成树上可以构造一个笛卡尔树，根结点表示最小生成树中的权值最大的边，撤去此边会将最小生成树分割为两个子树，笛卡尔树递归地从这两棵子树上构造。笛卡尔树的叶结点表示度量空间内的点，两个叶结点的最低公共祖先则是这两个点在最小生成树中最重的边，代表这两点间的距离。获得了最小生成树及将边按照权值排序后，笛卡尔树即可在线性时间内构造出来。

treap

笛卡尔树是二叉树，对于数列而言将其作为二叉搜索树是自然的。若将二叉搜索树结点关联上一个权值，并且保证此权值在树结构中遵循堆中的序关系，即父结点权值比子结点权值大，则此二叉搜索树又被称为Treap. 其名称来源于树与堆两英文词的组合（tree ＋ heap -> treap）。Treap与笛卡尔树在结构上是相同的，只是两者的应用不同。

笛卡尔树

何为笛卡尔树？

对于一组关系 $f a, l s, r s$

满足 $p r i [f a] ⩾ m a x (p r i [l s], p r i [r s])$

以及 $v a l [r s] ⩾ v a l [f a] ⩾ v a l [l s]$

如何构建笛卡尔树？

按照 $v a l$

那么，新插入的点一定会插入到最右边(最大)

那么，我们维护最右链

同时，注意到最右链中 $p r i$

因此可以维护一个单调栈，来即时地找到插入位置

void Tree() {
    for(int i = 1; i <= n; i ++) {
        pri[i] = rand();
        while(top && pri[s[top]] > pri[i])
        ls[i] = s[top], top --;
        fa[i] = s[top]; fa[ls[i]] = i; 
        if(fa[i]) rs[fa[i]] = i;
        s[++ top] = i;
    }
}

建树的方法2

每次选取区间最大值作为根，然后往两边递归也可以建树

直接暴力是 $O (n^{2})$

线段树优化一下就可以 $O (n \log n)$

一些常见的题目：

虚树

在一棵树中，把给定点及相关的 $l c a$

定理一：
树中 $k$

考虑 $d f s$

按照 $d f s$

那么，点 $a$

只要用一个单调栈来维护当前链即可

同时，为了方便，约定退栈连边

具体而言，有以下几种情况

我们假设 $v$

$r o o t$

技术分享图片
假设原链的形式类似于此

第一种情况：
技术分享图片
这种情况下， $v$

第二种情况：
技术分享图片
$a$

第三种情况：
技术分享图片
$v$

第四种情况：
技术分享图片
$v$

因此，总结一下步骤

先插入虚树根

依次插入后 $i$

求出 $a$

如果 $l c a = v$

如果 $d f n [w] >= d f n [l c a]$

如果 $d f n [w] < d f n [l c a]$

$a$

重复第 $2$

最后处理栈中剩下的最后一条链

给个本人的实现吧....

inline bool cmp(int a, int b) { return dfn[a] < dfn[b]; }

//dfn数组为dfs序，dep数组为节点深度
//h数组存储所有的关键点，总共有K个
//st为栈
void Vitural_Tree {
    sort(h + 1, h + K + 1, cmp);
    st[top = 1] = 1;
    for(ri i = 1; i <= K; i ++) {
        int rem = lca(st[top], h[i]);
        if(rem == st[top]) { st[++ top] = h[i]; continue; }
        while(top > 1 && dep[st[top - 1]] >= dep[rem])
        { link(st[top - 1], st[top]); top --; }
        if(dep[st[top]] > dep[rem]) link(rem, st[top]), top --;
        if(rem != st[top]) st[++ top] = rem; 
        if(h[i] != st[top]) st[++ top] = h[i];
    }
    while(top > 1) link(st[top - 1], st[top]), top --;
}