Dynamic Tree

前置知识：线段树

创新互联-专业网站定制、快速模板网站建设、高性价比宁洱网站开发、企业建站全套包干低至880元,成熟完善的模板库,直接使用。一站式宁洱网站制作公司更省心,省钱,快速模板网站建设找我们，业务覆盖宁洱地区。费用合理售后完善，十多年实体公司更值得信赖。

Splay

维护区间翻转，\(O(n)=10^6\)

显然，这样的操作不能用线段树来维护，因为线段树的结构是固定的，我们需要一种结构上更加灵活的数据结构

于是联想到平衡树，如果以，对于一个区间 \([l,r]\)，我们只需要知道 \(l-1\) 和 \(r+1\) 在平衡树上的位置就可以了，其中间的部分就是翻转的区间

如果翻转的区间是一颗子树，打一个标记表示子树翻转就可以了（注意第 \(x\) 个应该是在平衡树上找第 \(x\) 大）

但正常的平衡树不能使得翻转的区间总在一颗子树上，所以引出了 \(Splay\)

\(Splay\) 基于一个朴实的想法，需要操作的点如果是根那就会很方便，那么在操作时可以先把需要操作的点一路旋转到根就可以了（为了避免被卡，旋转应该有 \(6\) 种，比较繁琐）

如果涉及新的节点（比如插入），只需要找到前驱和后继，依次转到根上，发现前驱和后继之间没有点，然后就可以 \(\Theta(1)\) 插入了

于是翻转区间实际上是一样的，把前驱和后继换成第 \(l-1\) 大和第 \(r+1\) 大就会发现它们之间就是代表区间 \([l,r]\) 的子树

复杂度证明

既然 \(Splay\) 能维护区间翻转这种线段树做不到的事，那它显然也可以维护线段树能维护的信息（区间和、区间max之类的），只需要转出区间打 \(tag\)，旋转的时候 \(pushup\) 一下就好了

LCT

换根，维护 \(LCA\)

实际上可以看做求一个无根树上的‘Y’字形的拐点位置，而拐点处的点是距离'Y'字三点距离和最小的点，也就是

\[dis(a,b)=\text{a,b在树上的距离}\\ \text{设}f(x)=(dis(u,x)+dis(v,x)+dis(root,x))\\ f_{min}=f(LCA(u,v)) \]
当前文章：树论笔记
分享地址：http://cdkjz.cn/article/dsoipod.html