树

建议阅读顺序（有些没有严格的顺序关系）：

线段树 (ightarrow) 轻重链剖分（长短链剖分） (ightarrow) (LCA&LA) (ightarrow) 全局平衡二叉树 (ightarrow) 动态树

数据结构

线段树

https://www.cnblogs.com/efX-bk/p/segment_tree.html

动态树

https://www.cnblogs.com/efX-bk/p/basic_dynamic_tree.html

全局平衡二叉树

需要会树链剖分

先重链剖分，重链剖分中，跳轻边的次数为 (O(log n)) 的，然后用一个数据结构（线段树之类的）维护了重链上的信息

但在重链上维护信息可以做到更优，考虑把重链表示成一颗二叉树，满足：

1.这棵树的中序遍历是重链按深度遍历的结果，

2.二叉树上的节点关于轻子树的大小是最平衡的

第一点容易满足，第二点可以用更为形象的解释：把重链转为序列，以每个点轻子树的大小+1 为加权求加权中点作为根，然后递归到左右两边

称二叉树上的边为重边，其余边为轻边

由于是重链剖分，跳一次轻边 (size_{当前点}) 至少加倍，至多跳 (O(log n)) 次

由性质2，跳一次重边 (size_{ ext{轻子树}}) 至少加倍，至多跳 (O(log n)) 次

于是一共只会跳 (O(log n)) 次，但比起重链剖分的好处是我们用子树替代了序列，而子树操作常常容易做到 (O(1))（细节还是很多的，比如要判断有没有右子树什么的）

上面说的只适用于链的操作，如果是子树操作就需要把所有轻儿子往上放，访问到时就取出来，子树操作就对于所有轻儿子都打一个标记，重儿子特判一下

Trick

轻重链剖分

从某个点出发 dfs 整颗树，遇到一个新点就给它一个新的编号，这样一个子树就是连续的一段编号，这种方式被称为 (dfs) 序

(dfs) 序虽然解决了子树问题，但不能解决链上的问题，考虑把一条链拆成若干段连续的 (dfs) 序

(siz_x) 表示以 (x) 为根的子树的大小

定义一个点 (u) 所有子树中 (siz) 最大的是 (u) 的重儿子，记为 (son_u)，其他儿子都是轻儿子

这样，从一个点出发，我们优先遍历重儿子，这样显然不会破坏 (dfs) 序的性质

一个点到重儿子的边记为重边，其他边记为轻边

发现

[siz_{son}>siz_{ ext{轻儿子}}
siz_u=siz_{son_u}+sum siz_{u ext{的轻儿子}}
]