树链剖分
由于之前一直在颓废所以咕咕咕了很久呢, 这一篇主要是讲树 (重) 链剖分的, 长链剖分就等窝会了再更咯 qwq.
窝怎么知道. 树剖是一种数据结构, 可以快速维护树上的问题. 单次操作的时间复杂度是 $$O(nlog_n)$$. 树链剖分会把一棵树对应成一个序列, 再用线段树维护. 对于子树, 一个节点的子树就是一段区间, 直接区间操作就可以了; 对于一条路径, 它会对应多个区间, 而窝们要做的就是让它对应尽可能少的区间. 如图:所以
16
10
owo
蛤mo-ha
