浅析树链剖分

· · 个人记录

注意：本文默认读者已经掌握了线段树。

小引

GIFBMP种了一颗树。

现在有四个操作：

1.把x号节点到y号节点上的路径上的所有点的点权全部增加k。
2.求出x号节点到y号节点上的路径上的所有点的点权之和。
3.把x号节点的所有子树节点的点权全部增加k。
4.求出x号节点的所有子树节点的点权之和。

对于3,4号操作，我们可以直接求出这棵树的dfs序，然后线段树暴力修改/查询即可。

对于1,2号操作，我们可以先求出他们的LCA，然后一个一个点修改/查询。

GIFBMP出了一条毒瘤的链，把一次暴力修改/查询卡成了\Theta(nlogn)。

那么，我们该怎么办？

请看下文。

一、名词解析

1.1:轻重儿子：一个节点的重儿子是指它的所有儿子中子树大小最大的儿子，如果某个儿子不是重儿子，它就是轻儿子。

1.2:重链：如果树上一条链上的节点都是重儿子，这条链被称为重链。

如下图，用粗点标出的是重儿子。

二、预处理

我们需要维护以下信息：

1.dep[i]:表示节点i的深度。

2.f[i]:表示节点i的父亲节点。

3.size[i]:表示节点i的子树大小。

4.h[i]:表示节点i的重儿子的编号。

这些信息只用一遍\text{dfs}就可以实现，时间复杂度\Theta(n)。

Code：

void dfs1(int x,int fa){
    f[x]=fa;
    size[x]=1;
    dep[x]=dep[fa]+1;
    int tmp=-1;
    for(int i=fir[x];i;i=next[i]){
        int v=to[i];
        if(v==fa)
            continue;
        dfs1(v,x);
        size[x]+=size[v];
        if(size[v]>tmp){
            tmp=size[v];
            h[x]=v;
        }
    }
}

维护完这些信息后，我们还要维护一下几个信息：

1.top[i]:表示节点i所在的重链的顶点。

2.id[i]:表示节点i在\text{dfs}中是第几个被遍历到的。

3.loc[i]:表示第i个被遍历到的点的编号（方便建树）。

为了接下来的操作处理方便，在dfs中优先遍历重儿子。

Code:

void dfs2(int x,int fa){
    top[x]=fa;
    id[x]=++cnt;
    loc[cnt]=x;
    if(!h[x])
        return ;
    dfs2(h[x],fa);
    for(int i=fir[x];i;i=next[i]){
        int v=to[i];
        if(v==h[x]||v==f[x])
            continue;
        dfs2(v,v);
    }
}

线段树建树Code(以求和为例):

void build_tree(int o,int l,int r){
    if(l==r){
        sum[o]=val[loc[l]];
        return ;
    }
    int mid=l+r>>1;
    build_tree(o<<1,l,mid);
    build_tree(o<<1|1,mid+1,r);
    sum[o]=sum[o<<1]+sum[o<<1|1];
}

三、操作实现

再考虑小引中的四个操作：

1.把x号节点到y号节点上的路径上的所有点的点权全部增加k。
2.求出x号节点到y号节点上的路径上的所有点的点权之和。
3.把x号节点的所有子树节点的点权全部增加k。
4.求出x号节点的所有子树节点的点权之和。

对于1,2号操作，我们在\text{dfs}的时候容易发现，一条重链上的节点编号是连续的。

还记得小引中的的暴力算法吗？

我们可以优化一下这个算法。

模仿倍增求LCA的方法，不断跳跳跳，跳到同一条重链上的时候，深度小的点就是x,y的LCA。

首先，找LCA的过程中是可以边跳边修改/查询的，而且，因为一条重链上的节点id是连续的，我们很容易将一次修改/查询优化到\Theta(log^2n)。

最后由于跳LCA的过程中，最后跳到同一条重链上的时候，还有一段区间没被修改/查询，直接操作即可。

至于证明，我不会。

Code:

void updatepath(int x,int y,int k){
    while(top[x]!=top[y]){
        if(dep[top[x]]<dep[top[y]])
            swap(x,y);
        update(1,1,n,id[top[x]],id[x],k);
        x=f[top[x]];
    }
    if(dep[x]>dep[y])
        swap(x,y);
    update(1,1,n,id[x],id[y],k);
}
int querypath(int x,int y){
    int ret=0;
    while(top[x]!=top[y]){
        if(dep[top[x]]<dep[top[y]])
            swap(x,y);
        ret+=query(1,1,n,id[top[x]],id[x]);
        x=f[top[x]];
    }
    if(dep[x]>dep[y])
        swap(x,y);
    ret+=query(1,1,n,id[x],id[y]);
    return ret;
}

对于3,4号操作，我们可以发现，对于任意一棵子树，里面包含的节点的编号是连续的，所以，我们只需修改一次即可，时间复杂度\Theta(logn)。

Code:

void updateson(int x,int k){
    update(1,1,n,id[x],id[x]+size[x]-1,k);
}
int queryson(int x){
    return query(1,1,n,id[x],id[x]+size[x]-1);
}

四、补充

树剖除了重链剖分以外还有长链剖分的写法，但由于很冷门所以不讲。