[]树链剖分

写点东西记录一下，起码让自己记得自己曾经对树链剖分挺有兴趣:)

首先来看一道题：[BZOJ1036]树的统计

最暴力的做法就是直接修改，然后查询时两个节点往上跳到lca

这样做会很慢，因为它是O(树高)的，随便出个链的数据就能卡掉

所以我们想要每次往上跳很多层，这样跑起来会快一些

也就是顺着“树链”往上跳

我们询问$14\cdots10$的路径，只需跳$(14\cdots12)+[12\cdots9]+(9\cdots1)+(10\cdots3)+[3\cdots1]$

树链剖分不是一种具体的算法，而是一种思想

它把整棵树剖分成许多链，并且用数据结构（比如线段树）维护每一条链

于是（往上跳很多层）=（数据结构的区间操作）

既然要顺着链往上跳，我们应该先把树剖分成一些链

常用的方法是"重链剖分"

把一个节点的（子树大小最大的儿子）称为"重儿子"，其余儿子称为"轻儿子"

一个节点向它重儿子连的边称为"重边"，其余边称为"轻边"

如果当前节点为$x$，边$(fa[x],x)$为轻边，那么显然$size[fa[x]]\geq2\cdot size[x]$

所以从某个节点向上跳最多经过$O(log_2n)$条轻边

往上跳的过程中，由于轻边和重链交替出现，所以经过重链的数量级也是$O(log_2n)$的

挺快的，是吧？

剖分的方法也很简单，两次dfs就可以了

第一次记录深度$dep$，子树大小$siz$，重儿子$son$，父亲$fa$

第二次记录节点在数据结构中的位置$pos$，所属重链的顶端$bl$

dfs完建立数据结构，一般常用线段树或树状数组

查询/修改路径时顺着重链向上跳的同时在数据结构内做区间操作

具体点，查询/修改路径$x$到$y$

让$dep[bl[x]]\geq dep[bl[y]]$（深度大的先往上跳）

对区间$[pos[bl[x]],pos[x]]$操作（这条重链）

让$x=fa[bl[x]]$（同时跳过一条重链和一条轻边）

重复上述过程直到$bl[x]=bl[y]$（在同一条重链上）

最后对区间$[pos[x],pos[y]]$操作（一条重链上的剩余部分）

于是我们就可以愉快地解决路径的问题了w

子树呢？

观察第二个dfs，我们发现一个子树内的节点在数据结构上的位置都是连续的

所以对以$x$为根的子树操作就直接在数据结构内对$[pos[x],pos[x]+siz[x]-1]$就可以了

于是我们也可以愉快地解决子树的问题了w

就是这样喵

最后的一点小补充：

因为每次找$O(log_2n)$条重链

在重链上用数据结构进行操作的时间复杂度是$O(log_2n)$的

所以......你懂的，树链剖分每次操作的时间复杂度是$O(log_2^2n)$

但其实其中的一个$log$是上界，一般达不到

所以一般情况下没有出题人会丧心病狂到出数据卡这个$log_2^2n$，所以把它当$log_2n$用就好