一 点睛
常见的操作有序列操作和树上操作。
1 序列操作
通常采用线段树或伸展树(Splay Tree,Splay 树)。
2 树上操作
通常采用树链剖分或动态树。
二 动态树
动态树是动态的,维护一个由若干无序的有根树组成的森林,支持对某个节点到根的路径操作,以及对某个节点的子树操作,还支持换根、加/减边、子树合并/分离等。以 RobertE.Tarjan 为首的科学家们提出了 Link-Cut Trees(LCT),LCT 是最常见的一种解决动态树问题的工具。
1 树链剖分
为轻重链剖分,节点到重儿子(子树节点数最多的儿子)之间的路径为重链,一般采用静态数据结构如线段树或树状数组维护重链,静态数据结构无法解决动态问题。
2 LCT 为虚实链剖分
虚实链是动态变化的,每个实链都由一棵伸展树维护,所有伸展树就像一个森林,由虚边连接在一起组成一棵 LCT。
三 LCT
一棵 LCT 有以下性质。
1 一个节点到其子节点最多有一个实边,其他均为虚边。
2 每棵伸展树都维护一条按原树深度严格递增的实链。
3 每个节点都被包含且仅被包含在一棵伸展树中。
四 示例
1 原树
假设一棵树划分虚实边后如下图所示,图中一共有 7 条实链:A-B-D、E、C-F-I-M、L-N、G、J、H-K。每条实链都由一棵伸展树维护,按照在原树中的节点深度有序。
2 LCT
将上述 7 条实链分别构建 7 棵伸展树,每棵伸展树的根都与该实链的父节点通过虚边连接起来,LCT 如下图所示。
伸展树之间的连接“认父不认子”,在原树中,实链 C-F-I-M 的父节点为 A。在 LCT 中,实链 C-F-I-M 构建的伸展树的根为 F,树根 F 向该链的父节点 A 连一条边,表示该链的父节点为 A,然而 A 在原树中的儿子并不是 F。实链 C-F-I-M 对应的伸展树是动态变化的,但其父节点是不变的。LCT之所以被称为动态树,是因为它具有动态变化性:
a LCT 中的虚实边是动态变化的。
b 伸展树也是动态变化的,可以随时旋转,只要满足原树中的节点深度有序即可。
无论如何虚实变换、旋转,所有节点的相对位置都不变。若原树节点 x -y 路径上没有节点 z ,则操作完以后,在 x -y 路径上也不可能出现 z。