数链剖分

给一棵树，树链剖分后，树上任意一条链上的节点都可以用O(logn)个连续的区间表示。

声明：

参考课件来自宋泽宇（我不认识的...），讲授来自Accelerator

定义

一个点的：size表示子树中包括改点本身的节点个数，重儿子表示儿子中size最大的点

一个点和它重儿子之间的边为重边， 除重边的其他边为轻边。

重边构成的链为重链（最上面的重儿子他爸也在重链上）。

性质

一个点只能在且一定在一条重链上（叶子相当于一个重链）

因为每个点只能有一个重儿子，所以两个重链不会相交

定义一个点的top为该点所在重链中深度最小的点。

步骤

首先，dfs根节点找重儿子

void dfs1(int x, int fa) {
    a[x].deep = a[fa].deep + 1;
    a[x].size = 1;
    a[x].fa = fa;
    for(int i = head[x]; i; i=e[i].next ) 
        if(e[i].y != fa) {
            dfs1(e[i].y , x);
            a[x].size += a[e[i].y ].size ;
            a[x].son = a[a[x].son ].size > a[e[i].y].size ? a[x].son : e[i].y ;
        }
}

之后，再dfs一遍找到每个点的top

如果要用数据结构维护序列还需要处理出每个点在序列上的位置

void dfs2(int x, int tp) {
    a[x].in = ++clock;
    a[x].tp = tp;
    if(a[x].son ) dfs2(a[x].son , tp);//如果有重儿子要先dfs重儿子（叶子节点木有
    for(int i = head[x]; i; i = e[i].next ) 
        if(e[i].y != a[x].son && e[i].y != a[x].fa ) //注意判断是不是重儿子（没必要dfs）和祖先（不能dfs） 
            dfs2(e[i].y , e[i].y );
    a[x].out = clock;//??
}

(偷偷补一个课件觉得简单所以没写，而我又刚学的知识：

in,out为树链剖分序（一种dfs序），对于找 i 的子树，对 i 的子树求和，i 子树加这些操作，只需对这样的 j 修改/查询, 即满足in[i] <= in[j] <= out[i]）

对于一条链上的询问，每次让top深度大的点跳到这个点的top的父亲

并处理从这个点到它的top这段重链。直到两个点的top相同。

此时处理两点之间的这段重链。

证明：

关于链上询问做法的证明：

由于dfs时优先处理每个点的重儿子

故一条重链在序列上是连续的一段区间。

复杂度证明：

每次跳到top的父亲都会走一条轻边。会使子树大小至少扩大2倍

故有O(logn)段区间。

lca：

两个点top相同后深度小的点一定是原来两点的lca

树链剖分

原文：https://www.cnblogs.com/tyner/p/11374070.html