树链剖分学习笔记

· · 个人记录

一棵树，支持：

  1. 路径加
  2. 单点查询

一般树上链的问题使用树链剖分解决。

重链剖分

前置知识

LCA，线段树

定义

重儿子：所有儿子中子树最大的儿子为重儿子

重边：重儿子之间的连边

重链：若干重儿子连成的链

性质

一棵树可以被剖成若干重链。

优先遍历重儿子，所有重链的dfs序连续。

重链数量不多于 \log_2 个。

一条链上经过的重链个数不多于 \log_2 个。

我们可以通过线段树维护一段重链的信息。

枚举链上的重链，查询可以做到 \log^2。

实现

预处理

int fat[100001],siz[100001],dep[100001],hson[100001],top[100001],cnt,dfn[100001],dis[100001];
void getdfsh(int u,int fa) //获取：父节点，深度，子树大小，重儿子 
{
    fat[u]=fa;
    dep[u]=dep[fa]+1;
    int lll=0;
    for(int i=0;i<g[u].size();i++)
    {
        int v=g[u][i];
        if(v==fa) continue;
        getdfsh(v,u);
        if(siz[v]>lll)
        {
            hson[u]=v;
            lll=siz[v];
        }
        siz[u]+=siz[v];
    }
    siz[u]++;
}
void gettd(int u,int fa) //获取：链顶，dfs序 
{
    dfn[u] = ++cnt;
    dis[u] = cnt;
    if(hson[fat[u]]==u)
    {
        top[u]=top[fa];
    }
    else
    {
        top[u]=u;
    }
    if(hson[u]!=0) gettd(hson[u],u); //优先重子 
    for(int i=0;i<g[u].size();i++)
    {
        int v=g[u][i];
        if(v==fa||v==hson[u]) continue;
        gettd(v,u);
    }
}

修改与查询

int addlsum(int st,int ed,int v) //修改一条链，满足 lca(st,ed)=ed
{
    if(dfn[st]<dfn[ed]) swap(st,ed); //交换
    int u=st,re=0;
    while(1)
    {
        if(dfn[top[u]]<=dfn[ed]) //当前重链顶超过终点了
        {
            add(1,1,n,dfn[ed],dfn[u],v);
            break; //跳出
        }
        add(1,1,n,dfn[top[u]],dfn[u],v);
        u=fat[top[u]];
    }
    return re;
} 
int getlsum(int st,int ed) //查询一条链的和 同上
{
    if(dfn[st]<dfn[ed]) swap(st,ed);get(1,1,n,dfn[ed],dfn[st]);
    int u=st,re=0;
    while(1)
    {
        if(dfn[top[u]]<=dfn[ed])
        {
            re+=get(1,1,n,dfn[ed],dfn[u]);
            break;
        }
        re+=get(1,1,n,dfn[top[u]],dfn[u]);
        u=fat[top[u]];
    }
    return re;
}

长链剖分

长链即按深度剖分，主要解决深度问题，如 k 级祖先。