学习动态树, 我们首先需要了解到什么是 Splay, 推荐这一篇大聚聚 yyb 的博客.
我们在 LCT 中列写的 Splay 会以 yyb 的 splay 为基础作出改变, 也是方便大家的后继学习, 这样的排版.
LCT 主要解决什么问题呢?
维护一个数据结构, 支持以下操作:
查询一个点的父亲
查询一个点所在的树的根
修改某个节点的权
向从某个节点到它所在的树的根的路径上的所有的节点的权增加一个数
查询从某个节点到它所在的树的根的路径上的所有的节点的权的最小值
把一棵树从某个节点和它的父亲处断开, 使其成为两棵树
让一棵树的根成为另一棵树的某个节点的儿子, 从而合并这两棵树
把某棵树的根修改为它的某个节点
查询在同一棵树上的两个节点的 LCA
修改以某个节点为根的子树的所有节点的权
查询以某个节点为根的子树的所有节点的权的最小值
那么, 既然是在一颗或者多棵树上维护这样的数据结构, 我们势必要现有一棵树, 但是这棵树又过于灵活了, 我们就想到了一种树链剖分的形式)-- 实链剖分. 这也是穿插起整个 Splay 的最重要的纽带, 我们把一棵树拆成几个 Splay 的形式, 这即可满足这样的条件, 在一颗 splay 上的点都是一条重链上的, 也就是代表着一条重链上的点都在一颗 splay 上面.
但是这样的重链同时又是灵活的, 我们有时候需要去拆掉它, 也有可能得将一条轻链变成一条重链, 并且拆掉原来的重链变轻成为轻链.
现在, 我们首先要来了解一下 LCT 的三个性质:
LCT 的主要性质如下:
每一个 Splay 维护的是一条从上到下按在原树中深度严格递增的路径, 且中序遍历 Splay 得到的每个点的深度序列严格递增.
是不是有点抽象哈
比如有一棵树, 根节点为 11(深度 1), 有两个儿子 2,32,3(深度 2), 那么 Splay 有 33 种构成方式:
{1−2},{3}{1−2},{3}
{1−3},{2}{1−3},{2}
{1},{2},{3}{1},{2},{3}(每个集合表示一个 Splay)
而不能把 1,2,31,2,3 同放在一个 Splay 中(存在深度相同的点)
每个节点包含且仅包含于一个 Splay 中
边分为实边和虚边, 实边包含在 Splay 中, 而虚边总是由一棵 Splay 指向另一个节点(指向该 Splay 中中序遍历最靠前的点在原树中的父亲).
因为性质 2, 当某点在原树中有多个儿子时, 只能向其中一个儿子拉一条实链(只认一个儿子), 而其它儿子是不能在这个 Splay 中的.
那么为了保持树的形状, 我们要让到其它儿子的边变为虚边, 由对应儿子所属的 Splay 的根节点的父亲指向该点, 而从该点并不能直接访问该儿子(认父不认子).
接下去, 认识几个 LCT 的独有的函数:
access(x)函数, 将 x 到根节点的边全部划成重链. 做法也不是很难, 不断的把到根节点上的轻链变重, 然后原本的重链变轻即可.
转到根;
换儿子;
更新信息;
当前操作点切换为轻边所指的父亲, 转 1
就是这样的几步, 就构成了 access(x)操作.
- inline void access(int x)
- {
- int y = 0;
- while(x)
- {
- splay(x); c[x][1] = y;
- pushup(x);
- y = x; x = fa[x];
- }
- }
然后再看, 就是把某一个节点变成原树的根这样的一个操作.
- inline void makeroot(int x)
- {
- access(x); splay(x);
- pushr(x);
- }
但是这里有一个 pushr(x), 这是个什么操作呢? 因为原本上 x 的深度是最深的, 所以反转到 splay 树的顶端的时候, 也一定是只有左儿子, 所以, 假如将它下面的所有的点都翻转一遍之后, 就是将 x 变成了最浅的, 也就是真正的树的根了.
inline void pushr(int x) { swap(c[x][0], c[x][1]); r[x] ^= 1; } // 翻转操作
接下去的操作, 我们可以看到既然可以制造根了, 那么也就是意味着可以找根了呀. 我们需要找到这样的原树中的深度最浅的节点. findroot(x)==findroot(y)表明 x,yx,y 在同一棵树中.
- int findroot(int x)
- {
- access(x); splay(x);
- while(c[x][0]) { pushdown(x); x = c[x][0]; }
- splay(x); // 保证时间复杂度
- return x;
- }
这里呢, 又有一个 pushdown(x)这样的一个操作, 那么这个操作是干什么的呢? 就是向下传递信息的而已.
- inline void pushdown(int x)
- {
- if(r[x])
- {
- if(c[x][0]) pushr(c[x][0]);
- if(c[x][1]) pushr(c[x][1]);
- r[x] = 0;
- }
- }
其中, r[x]就是一个延时标记而已.
那么, 有时候, 我们需要一段 x-y 这样的链怎么办, 我们是不是需要考虑把这段链给拉出来? 这时候出现的函数叫做 split(x, y)函数. 将 x-y 的路径拉成一条 splay.
- inline void split(int x, int y) // 把 x-y 的这条边提取出来
- {
- makeroot(x);
- access(y); splay(y);
- }
还有就是我们要连接边的时候, 就是将两个块连接起来的时候, 就是需要加上一个 link(x, y)操作, 假如 x,y 原先不在同一棵原树上, 那么就是可以把 x,y 这样的一条边给连接起来了.
- inline void link(int x, int y) // 连边
- {
- makeroot(x);
- if(findroot(y) != x) fa[x] = y;
- }
接下去还要处理一个断开一条 (x,y) 直接连接的这条边, 将 x,y 断开(不是断开两个块, 就是断开这条线).
先判一下连通性 (注意 findroot(y)findroot(y) 以后 xx 成了根), 再看看 x,yx,y 是否有父子关系, 还要看 yy 是否有左儿子.
因为 access(y)access(y)以后, 假如 y 与 x 在同一 Splay 中而没有直接连边, 那么这条路径上就一定会有其它点, 在中序遍历序列中的位置会介于 xx 与 yy 之间.
那么可能 yy 的父亲就不是 xx 了.
也可能 yy 的父亲还是 xx, 那么其它的点就在 yy 的左子树中
只有三个条件都满足, 才可以断掉.
当然, 我们也可以维护一下 size, 如果存了的话. 因为就剩下 x,y 两个点了我们只需要判断在 splay 最上面的那个点的 size 与 2 的大小比较即可.
- inline void cut(int x, int y)
- {
- makeroot(x);
- if(findroot(y) != x || fa[y] != x || c[y][0]) return;
- fa[y] = c[x][1] = 0;
- pushup(x);
- }
来源: http://www.bubuko.com/infodetail-3077406.html