Link Cut Tree

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

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

Structure......

president-tree-learning

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

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

可持久化线段树

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

可持久化数据结构

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

可持久化线段树......