Link Cut Tree

动态树(Dynamic Tree Problems)是一类要动态维护森林连通性问题的总称。一般要维护森林中某个点到根结点的某些数据,应该支持一棵树切割成两棵树,或者两棵树合并成一棵树的操作。而解决这一类问题的基础数据结构就是LCT。

整体维护的过程有点类似于树链剖分的维护过程,不过树链剖分里维护的重链由于是静态的,可以用线段树去维护。对于动态的,我们可以用splay来维护。

Structure

我们用操作access(x)来表示访问节点x。那么定义:

Preferred Child:对于一个节点P,如果最后被访问的节点x在以其子节点Q为根的子树中,那么就称Q为P的Preferred......

president-tree-learning

主席树我的理解是可持久化线段树的一种应用吧。本质上就是可持久化线段树,不过我们在查询的时候用到了他们之间可以相减的性质。

首先介绍一下可持久化线段树。

可持久化线段树

可持久化线段树是可持久化数据结构中的一种,主席树的实现就是利用了可持久化线段树的。

可持久化数据结构

所谓的可持久化数据结构,就是保存这个数据结构的历史版本,同时应该公用他们的公有部分来减少内存上的消耗。

可持久化线段树

在每次更新的时候,我们保存下来每次更新的历史版本,以便我们之后查阅。在主席树中我们用到的线段树是保存当前范围内位置有多少个数的。以下都用这个当例子。

下面图中点的表示:

建树

建立一颗空树......