欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

树链剖分的学习理解

程序员文章站 2024-02-14 09:49:52
...

【前言】

本文仅为本人学习树链剖分的理解和总结,有误之处请大佬指点迷津。也有与其他博客不同或矛盾之处。

【树链剖分】

顾名思义,将树结构,剖分成链状结构,然后将一条条的链拼接成线性结构,然后就可以通过线段树、树状数组等维护了。

说白了就是在树上,有些值不好维护,通过树链剖分转化成一个序列,而序列就好维护了。

树链剖分做的事情就是把树映射成一个序列,让线段树去维护这个序列,以达到维护树的目的。

【剖分方法】

1.概念

重儿子:结点u的子结点中,拥有最大子树的那个儿子结点。

轻儿子:除了唯一的重儿子,其余都为轻儿子

重链:   从结点u向重儿子延伸下去,所形成的一条链

轻链:   去掉重链,剩下的那些链都是轻链,一般来说,轻链都是孤立的点。

图中粗边连接的链就是重链,其余为轻链。标记红点的点为重链的起点。边上的数字表示dfs时的顺序(一定要重链的dfs序连续)。

树链剖分的学习理解

2.设置数组

数组名 功能
dep[u] 树上结点u的深度(根结点为0)
dad[u] 树上结点u的父结点(假设根结点为本身)
siz[u] 树上结点u的子树结点数目(包括u本身)
son[u] 树上结点u的重儿子
top[u] 树上结点u的重链队长,即u所在的重链以top[u]为起点
rk[u] 树上结点u对应的序列位置下标
id[ i ]

序列上位置 i 对应的树上结点编号(基本无实际用处)

 

 

 

 

 

 

 

 

3.求出2中的所有数组

两次dfs,第一次dfs,求出dep,dad,siz,son,这四个很简单。第二次dfs求top,rk,id,这里需要注意dfs优先进入重儿子。

其实rk数组才是主角,我们按照dfs进行的顺序,给树上点编号,并且让重链的编号都是连续的(dfs2优先进入重儿子的原因),这样我们就能用线段树维护这段重链了。

/************ 树链剖分 **************/
int dep[MAX],dad[MAX],siz[MAX],son[MAX];
int top[MAX],rk[MAX],id[MAX];
void dfs1(int u,int pre)
{
    siz[u]=1; //u本身
    son[u]=-1;
    int maxsiz=0; //最大的儿子子树大小
    for(int i=head[u];i!=-1;i=edge[i].next)
    {
        int v=edge[i].t;
        if(v==pre)continue;
        dep[v]=dep[u]+1;
        dad[v]=u;
        dfs1(v,u); //注意dfs的位置
        siz[u]+=siz[v];
        if(maxsiz<siz[v])
        {
            maxsiz=siz[v];
            son[u]=v;
        }
    }
}
void dfs2(int u,int fat,int &tag) //结点u,重链顶端
{
    top[u]=fat;
    rk[u]=++tag; //时间戳
    id[tag]=u; //tag对应在树上的结点号
    if(son[u]==-1)return; //没有孩子
    dfs2(son[u],fat,tag); //优先重链dfs
    for(int i=head[u];i!=-1;i=edge[i].next)
    {
        int v=edge[i].t;
        if(v==dad[u]||v==son[u])continue;
        dfs2(v,v,tag);
    }
}
void cuttree(int root) //将root为根的树链剖分
{
    int tag=0;
    dep[root]=0;  //根的深度和父结点做一个初始化
    dad[root]=root;   //这是一个假设,根的父结点还是根
    dfs1(root,root);
    dfs2(root,root,tag);
}

4.修改操作

如果我们想对树上u-v之间的所有点的权值增加num,那么uv之间一定可以越过一些重链互相到达,那我们可以同LCA的思想处理。更新u-v,等同于更新u-v之间涉及到的重链,也就是线段树维护的一些区间。

void modify(int u,int v,ll num, int limit) //修改
{
    int fu=top[u],fv=top[v];
    while(fu!=fv) //uv不在同一条链上
    {
        if(dep[fu]>=dep[fv]) //u的深度大
        {
            update(rk[fu],rk[u],num,1,1,limit); //线段树更新这段区间
            u=dad[fu]; fu=top[u];
        }
        else
        {
            update(rk[fv],rk[v],num,1,1,limit);
            v=dad[fv]; fv=top[v];
        }
    } //循环结束时,fu-fv在同一链
    if(dep[u]>dep[v])swap(u,v);
    update(rk[u],rk[v],num,1,1,limit);
}

【练习题】

HDU3966  http://acm.hdu.edu.cn/showproblem.php?pid=3966

题解:https://blog.csdn.net/winter2121/article/details/81592775

相关标签: 树链剖分