LCT 动态树 最后更新于 2025-05-02 19:28:50

维护动态树的数据结构有三： ①LCT ②ETT ③Top Tree # ①LCT # 小说： 1. 每条重链单独使用一个平衡树进行维护。 3. LCT：实链剖分与平衡树维护动态树的信息，并且同时维护多个动态树，所以全局是森林。 5. 每个节点认定一个实儿子，然后把这条边看成实边，其他为虚边，然后忽视虚边，维护一堆链，如果需要别的操作，虚实边可以随时转换。 7. 通过一个个连边建树来建图，开始连的都是虚边，在以后通过 access 函数转实边，也许你觉得这时间复杂度不炸了？不急没炸。 # 概念： - 原树：原来的多叉树，方便观察原树形态。 - 辅助树：把一整个平衡树看成一个整块，用虚边连起来这些整块，方便观察各个平衡树形态。（一坨实链里是平衡树（二叉），然后虚边连了好几坨（多叉）） 为了方便，我把下面的单个平衡树（一坨实链）全说成辅助树了。 # 代码： 注意： 1. `link(x,y)` 和 `cut(x,y)` 如果不保证合法，就都要判合法。 ### …… —— FHQ 定义 ```cpp bool fx[300030]; struct treap {int l,r,fa,sui,xu,v,x;bool lan;} t[300030]; struct node {int x,y;}; ``` ### pushdown() —— FHQ 下传懒标记 懒标记之翻转：用于 `access()`，是必写的，同时也是为什么只能用 FHQ 和 splay 的原因。 ```cpp void pushdown(int o) { if(t[o].lan) swap(t[o].l,t[o].r),t[t[o].l].lan^=1,t[t[o].r].lan^=1,t[o].lan=0; } ``` ### updata() —— FHQ 更新 这里的异或是题目要求异或和。 ```cpp inline void updata(int o) { t[o].x=t[o].v^t[t[o].l].x^t[t[o].r].x; if(t[o].l) t[t[o].l].fa=o; if(t[o].r) t[t[o].r].fa=o; } ``` ### merge() —— FHQ 合并 ```cpp int hebing(int x,int y) { if(!x||!y) return x+y; if(t[x].sui<t[y].sui) return pushdown(x),t[x].r=hebing(t[x].r,y),updata(x),x; else return pushdown(y),t[y].l=hebing(x,t[y].l),updata(y),y; } ``` ### isroot() —— 是否是辅助树树根 ```cpp bool isroot(int o) {return (t[t[o].fa].l!=o&&t[t[o].fa].r!=o)||!t[o].fa;}} ``` ### findroot() —— 找辅助树的根 这里的 fx 数组同时记录分裂时的方向，因为要按 o 的位置分裂，所以用分裂要先用这个函数。 ```cpp int findroot(int o) { top=0; while(!isroot(o)) fx[++top]=(t[t[o].fa].l==o),o=t[o].fa; return o; } ``` ### findleft() —— 找当前辅助树中中序最小的 本质上是找辅助树在原树上深度最小的节点。 ```cpp int findleft(int o) { o=findroot(o),pushdown(o); while(t[o].l) o=t[o].l,pushdown(o); return o; } ``` 另一种写法直接省略此函数，直接用辅助树的根的 $fa[]$ 为原树深度最小的节点的父亲（fa 数组是 FHQ 的），如果按此方法写，可以用 `findroot()` + `fa[]` 解决。 复杂度是一样的，因为 `findroot()` 和 `findleft()` 复杂度一样。 但是 FHQ 貌似只能用 `findleft()`，splay 一般维护 fa 数组。 ### split() —— 改的 FHQ 分裂 在当前辅助树中把位置 $≤o$ 的分裂为左，余为右。 关于如何找 o 的位置，我们在分裂前必须用 findroot 来记录数组。 ```cpp void split(int o,int &l,int &r) { if(!top) return pushdown(o),l=o,r=t[o].r,t[o].r=0,updata(o),void(); bool d=fx[top--]; d^=t[o].lan,pushdown(o); if(d) r=o,split(t[o].l,l,t[o].l); else l=o,split(t[o].r,t[o].r,r); updata(o); } ``` ### access() —— 把当前节点到根全部改为实链 ```cpp int access(int o) { int last=0; while(o) { int shang,xia; split(findroot(o),shang,xia); t[findleft(last)].xu=0; last=hebing(shang,last); t[findleft(xia)].xu=o; o=t[findleft(last)].xu; } return last; } ``` ### root() —— 找当前节点所在原树的根 ```cpp int root(int o) {return findleft(access(o));} ``` ### changroot() —— 把当前节点改为原树的根 ```cpp void changeroot(int o) {t[access(o)].lan^=1;} ``` ### link() —— 连 x 到 y 的边 ```cpp void link(int x,int y) {changeroot(x),t[x].xu=y;} ``` ### cut() —— 切断 x 到 y 的边 ```cpp void cut(int x,int y) {changeroot(x),access(y),access(x),t[y].xu=0;} ``` ### query() —— 查询 这个代码是查询 x 到 y 的路径上的 xor 和： ```cpp int query(int x,int y) {return changeroot(x),access(y),t[findroot(y)].x;} ``` ### change() —— 修改 这个代码是将点 x 上的权值变成 y。 ```cpp void change(int o,int v) { changeroot(o); node tmp=split(findroot(o)); t[o].v=v,merge(tmp.x,tmp.y); } ``` ### solve() ```cpp cin>>n>>m; for(int i=1;i<=n;++i) cin>>t[i].v,t[i].x=t[i].v,t[i].sui=rand(); for(int i=1,op,x,y;i<=m;i++) { cin>>op>>x>>y; if(op==0) cout<<query(x,y)<<'\n'; else if(op==1&&root(x)!=root(y)) link(x,y); else if(op==2) cut(x,y); else if(op==3) change(x,y); } ``` # 优秀的时间复杂度 [挺好的证明](https://oi-wiki.org//ds/lct/) 时间复杂度 $O(nlogn)$，常数 $≈11.4514$。 以上复杂度是平衡树是 splay 的条件下，不过只要能维护翻转就行，所以可以牺牲一个 log 选择 FHQ，FHQ 常数更小了，写个快读表现就和 splay 差不多了。 splay ~~不会~~ 不好使，所以我就用 FHQ 了。 # LCT 使的地方： ### 1. 动态树问题（如话）。 ### 2. 大部分树链剖分操作。 #### 好处： - 在维护链用 splay 理论复杂度甚至更快，但是常树很大！树剖不理论复杂度很快。 - 比树剖套数据结构少码了。 #### 如果有人问我怎么维护子树： 我们就维护连通块的信息，然后把他跟他父亲的边删了，这样不就能查询子树了？ #### 如果你问我怎么维护连通块？那我就跟你说： 目前容易维护当前节点所在实链的 sum （相当于单个平衡树），若要维护整个原树的 sum 就需要用到一些方法： 这个我讲。 #### 坏处： 最好学的 LCT 动态树无法修改子树！！！令人伤心 ### 3. 支持删除边的并查集（需保证无环）。 找根操作。 ### 4. 可在线维护边权。（最小生成树之类）。 看题！ ### 5. 在线加边维护边双联通分量。 在 link 的时候，如果发现 x 和 y 在一个树里，有环，那肯定要开始缩了，锁点的时候，把这个环上的所有点全部锁到这个辅助树的根节点，因为可以把根节点的 fa 设为原树父亲，比较特殊，所以缩这里。 根节点为标志节点，用并查集代表当前节点被锁到哪去了，然后把当前环上的点提出来一个辅助树，然后递归这个辅助树更新并查集为标志节点，最后断开标志节点与子树的连接，同时在需要访问原树的父亲节点的时候，需要套用并查集，因为这个点的父亲可能已经被缩了。 函数递归缩点： ```cpp void del(int x,int y) {if(x) bcj[x]=y,del(lc,y),del(rc,y);} ``` 找爸爸： $ fa(x)←find(fa_x)$ ### 6. 维护树上染色联通块。 [看题！等会再看吧……](https://www.luogu.com.cn/problem/P2173) ### 7. 求 LCA ```cpp inline int access(int x) { int y = 0; while (x) { splay(x); Rs(x) = y; pushup(x); x = Fa(y = x); } return y; } int lca = (access(u), access(v)); ``` 我们拉完 u 到根的实链后再拉 v 的。则最后一个需要调整的实链顶对应的结点自然是 lca(u,v)。 在动态树上，你想写 LCA： #### 忍住别写： - 倍增 LCA：这个不行，这个 - 在动态树上跳链 LCA：在动态树上复杂度是均摊的，你普通跳链复杂度不对，（access 其实也是跳链，但是它一路上变了好多实链，这是不一样的地方）。 # LCT 屎的地方： ### 1. 忍住别想 !!! LCT 子树修改 因为只有 TopTree 可以子树修改，sone1 就是有子树修改，特别难根本写不了。 ### 2. 原树根不固定 所以你不要自以为是地 access！ # ②ETT \ \ \ \ \ # ③Top Tree \ \ \ \ \ # 刚刚接到通知！我已经被 ETT、Top Tree 淘汰了！ ###### [大体结构](https://oi-wiki.org//ds/lct/) [LCT 题单](https://www.cnblogs.com/flashhu/p/9498517.html) [【拓展】](https://www.cnblogs.com/flashhu/p/9498517.html) [【OI-WIKI】](https://oi-wiki.org//ds/lct/)