是什么

树链剖分,就是将一棵树划分为若干条互不相交的链,以做到快速维护树上信息。

此处研究的是轻重链剖分,可以实现如下操作:

  • xy 的路径上的点权全部加上 z
  • 查询 xy 的路径上的点权之和
  • 将以 x 为根的子树上的点权全部加上 z
  • 查询以 x 为根的子树上的点权之和

轻重链剖分可以使得每条链上的点的 dfs 序连续,因此可以很方便的使用线段树来处理区间修改区间查询问题。

实现

一些定义

  • 重儿子:非叶子节点的儿子节点中,子树大小最大的儿子节点
  • 轻儿子:剩下的就是轻儿子(叶子节点没有重儿子或轻儿子)
  • 重边:某节点与其重儿子的连边称为重边
  • 轻边:剩余的为轻边
  • 重链:重边首尾相接形成重链(落单的叶子结点也构成链)

就这样,一棵树就会被剖分成若干条互不相交的重链。

预处理

树剖的预处理需要进行两遍 dfs。

第一个 dfs 处理每个节点的父亲节点,深度,子树大小以及重儿子的初始编号,第二个 dfs 处理每个节点所在链的链顶以及其 dfs 序编号(即新的节点编号)。

由于我们需要使得每条链方便进行维护,所以每个节点需要按照其 dfs 序进行重新编号

dfs1

先给出一些定义:

int dep[maxn];//深度
int size[maxn];//子树大小(包括自己本身)
int fa[maxn];//父亲节点
int son[maxn];//重儿子节点

很明显,只需要扫描一遍树,自底向上更新子树大小以及重儿子编号,顺便记录深度即可。

void dfs1(int x,int father,int d)
{
    dep[x]=d;
    fa[x]=father;
    size[x]=1;
    int maxson=-1;
    for(auto y:G[x])
    {
        if(y==father)
            continue;
        dfs1(y,x,d+1);//先继续递归更新子树信息
        size[x]+=size[y];//更新子树大小
        if(size[y]>maxson)
            maxson=size[y],son[x]=y;//更新重儿子
    }
}

dfs2

给出如下定义:

int id[maxn];//节点的新编号
int w[maxn],wt[maxn];//前者存储旧编号对应的点权,后者存储新编号对应的点权
int cnt;//计数用
int top[maxn];//节点所在链的链顶

此时处理的顺序有要求:因为要使重链上的 dfs 序连续,所以在遍历子树时优先遍历重儿子。对于重儿子,链顶继承即可;对于轻儿子,链顶就初始化为其本身即可。

void dfs2(int x,int topf)//x 为节点编号,topf 为所在链顶节点编号
{
    id[x]=++cnt;//处理节点新编号
    wt[cnt]=w[x];//新编号对应的点权
    top[x]=topf;//更新该节点对应的链顶
    if(!son[x])
        return;//叶子结点就直接返回
    dfs2(son[x],topf);//先处理重儿子,链顶直接继承
    for(auto y:G[x])
    {
        if(y==son[x] || y==fa[x])
            continue;
        dfs2(y,y);//处理轻儿子,该儿子就是本身所在链的链顶
    }
}

线段树相关

线段树就是建立在 w[maxn] 上的,由于链上的相邻节点的新编号也是相邻的,所以直接在线段树上操作即可。

这里以树剖模板为例建一棵维护区间加区间和的线段树。

#define L (k<<1)
#define R (L|1)
#define M (i+j>>1)

int f[maxn<<2],tag[maxn<<2];

void build(int i,int j,int k)
{
    if(i==j)
    {
        f[k]=wt[i];
        if(f[k]>p)
            f[k]%=p;
        return;
    }
    build(i,M,L);
    build(M+1,j,R);
    f[k]=(f[L]+f[R])%p;
}

void down(int i,int j,int k)
{
    f[L]=(f[L]+tag[k]*(M-i+1)%p)%p;
    f[R]=(f[R]+tag[k]*(j-M)%p)%p;
    tag[L]+=tag[k],tag[R]+=tag[k];
    tag[k]=0;
}

void modify(int i,int j,int x,int y,int k,int d)
{
    if(x<=i && y>=j)
    {
        f[k]=(f[k]+d*(j-i+1)%p)%p;
        tag[k]+=d;
        return;
    }
    if(tag[k])
        down(i,j,k);
    if(x<=M)
        modify(i,M,x,y,L,d);
    if(y>M)
        modify(M+1,j,x,y,R,d);
    f[k]=(f[L]+f[R])%p;
}

int query(int i,int j,int x,int y,int k)
{
    if(x<=i && y>=j)
        return f[k];
    if(tag[k])
        down(i,j,k);
    int ans=0;
    if(x<=M)
        ans=(ans+query(i,M,x,y,L))%p;
    if(y>M)
        ans=(ans+query(M+1,j,x,y,R))%p;
    return ans;
}

如何修改和查询

注意:

  • 由于 dfs2 时先重儿子后轻儿子,所以每条重链上的编号是连续的
  • 由于是 dfs,所以子树的编号也是连续的

利用以上性质可以很方便的维护:

区间修改区间查询

处理两个节点之间的最短路径时,若两节点在同一条链上,十分好办,由于同一条链上编号连续,所以只需在线段树上区间处理即可。

若两个节点不在同一链上,

  1. 取链顶最深的节点(不然会跳到不知道哪里去的),处理其到链顶的信息,再将其向上跳到链顶的父亲节点。
  2. 重复以上操作知道两节点在同一链上为止。

区间查询的代码:

int query_range(int x,int y)
{
    int ans=0;
    while(top[x]!=top[y])//如果两节点不在同一条链上
    {
        if(dep[top[x]]<dep[top[y]])//保证 x 节点为链顶深度最深的节点
            swap(x,y);
        ans=(ans+query(1,n,id[top[x]],id[x],1))%p;//处理链顶到 x 的信息
        x=fa[top[x]];//将 x 跳到链顶的父节点
    }
    if(dep[x]>dep[y])//保证此时 x 的深度比 y 小
        swap(x,y);
    ans=(ans+query(1,n,id[x],id[y],1))%p;//处理两个节点跳到同一链上时的情况
    return ans;
}

区间修改和区间查询类似,只需要把线段树区间查询操作改为修改即可

void modify_range(int x,int y,int z)
{
    z%=p;
    while(top[x]!=top[y])
    {
        if(dep[top[x]]<dep[top[y]])
            swap(x,y);
        modify(1,n,id[top[x]],id[x],1,z);
        x=fa[top[x]];
    }
    if(dep[x]>dep[y])
        swap(x,y);
    modify(1,n,id[x],id[y],1,z);
    return;
}

子树修改子树查询

dfs 保证了子树内每一节点的编号都连续,所以对于一棵以 x 为根的子树的操作只需区间修改 [id(x),id(x+size(x)-1)] 即可。

int query_son(int x)
{
    return query(1,n,id[x],id[x]+size[x]-1,1)%p;
}

void modify_son(int x,int z)
{
    modify(1,n,id[x],id[x]+size[x]-1,1,z);
    return;
}

注意事项

  • 线段树数组开够
  • 线段树上的编号为新编号(即 dfs 序),处理查询和修改函数时都使用原编号
  • 每次查询或修改操作时要下放懒标记

其实也没啥,主要就是线段树别写炸了就行。

每条路径最多会被剖分成 \log n 条重链,而线段树一次操作复杂度为 O(\log n),所以区间修改查询的复杂度为 O(\log^2n),子树修改查询的复杂度为 O(\log n)

如果题目要求的是维护边权,那么可以将一条边的边权映射到它更深一端的节点上去,这样可以实现边和点的一一对应,继续使用线段树维护

但是由于在处理的时候我们不能处理到两节点的 lca,因为其 lca 映射到的是上面一条边,不在两点路径间,这时候只需要在上端节点的 dfs 序上加一即可解决

modify(1,n,id[a]+1,id[b],1);

例题

P3384 【模板】轻重链剖分

模板题,按照题意建维护区间和的线段树即可。

#include <cstdio>
#include <cctype>
#include <vector>
#define L (k<<1)
#define R (L|1)
#define M (i+j>>1)

inline int read()
{...}

inline void swap(int &a,int &b)
{...}

const int maxn=1e5+5;
int n,m,r,p,w[maxn],wt[maxn];
int id[maxn],dep[maxn],fa[maxn],son[maxn],size[maxn],top[maxn];
int cnt;
int f[maxn<<2],tag[maxn<<2];
std::vector<int> G[maxn];

void build(int i,int j,int k)
{
    if(i==j)
    {
        f[k]=wt[i];
        if(f[k]>p)
            f[k]%=p;
        return;
    }
    build(i,M,L);
    build(M+1,j,R);
    f[k]=(f[L]+f[R])%p;
}

void down(int i,int j,int k)
{
    f[L]=(f[L]+tag[k]*(M-i+1)%p)%p;
    f[R]=(f[R]+tag[k]*(j-M)%p)%p;
    tag[L]+=tag[k],tag[R]+=tag[k];
    tag[k]=0;
}

void modify(int i,int j,int x,int y,int k,int d)
{
    if(x<=i && y>=j)
    {
        f[k]=(f[k]+d*(j-i+1)%p)%p;
        tag[k]+=d;
        return;
    }
    if(tag[k])
        down(i,j,k);
    if(x<=M)
        modify(i,M,x,y,L,d);
    if(y>M)
        modify(M+1,j,x,y,R,d);
    f[k]=(f[L]+f[R])%p;
}

int query(int i,int j,int x,int y,int k)
{
    if(x<=i && y>=j)
        return f[k];
    if(tag[k])
        down(i,j,k);
    int ans=0;
    if(x<=M)
        ans=(ans+query(i,M,x,y,L))%p;
    if(y>M)
        ans=(ans+query(M+1,j,x,y,R))%p;
    return ans;
}

int query_range(int x,int y)
{
    int ans=0;
    while(top[x]!=top[y])
    {
        if(dep[top[x]]<dep[top[y]])
            swap(x,y);
        ans=(ans+query(1,n,id[top[x]],id[x],1))%p;
        x=fa[top[x]];
    }
    if(dep[x]>dep[y])
        swap(x,y);
    ans=(ans+query(1,n,id[x],id[y],1))%p;
    return ans;
}

int query_son(int x)
{
    return query(1,n,id[x],id[x]+size[x]-1,1)%p;
}

void modify_range(int x,int y,int z)
{
    z%=p;
    while(top[x]!=top[y])
    {
        if(dep[top[x]]<dep[top[y]])
            swap(x,y);
        modify(1,n,id[top[x]],id[x],1,z);
        x=fa[top[x]];
    }
    if(dep[x]>dep[y])
        swap(x,y);
    modify(1,n,id[x],id[y],1,z);
    return;
}

void modify_son(int x,int z)
{
    modify(1,n,id[x],id[x]+size[x]-1,1,z);
    return;
}

void dfs1(int x,int father,int d)
{
    dep[x]=d;
    fa[x]=father;
    size[x]=1;
    int maxson=-1;
    for(auto y:G[x])
    {
        if(y==father)
            continue;
        dfs1(y,x,d+1);
        size[x]+=size[y];
        if(size[y]>maxson)
            maxson=size[y],son[x]=y;
    }
}

void dfs2(int x,int topf)
{
    id[x]=++cnt;
    wt[cnt]=w[x];
    top[x]=topf;
    if(!son[x])
        return;
    dfs2(son[x],topf);
    for(auto y:G[x])
    {
        if(y==son[x] || y==fa[x])
            continue;
        dfs2(y,y);
    }
}

int main()
{
    n=read(),m=read(),r=read(),p=read();
    for(int i=1;i<=n;i++)
        w[i]=read();
    for(int i=1;i<n;i++)
    {
        int a=read(),b=read();
        G[a].push_back(b);
        G[b].push_back(a);
    }
    dfs1(r,0,1);
    dfs2(r,r);
    build(1,n,1);
    while(m--)
    {
        int opt=read(),x=read(),y,z;
        if(opt==1)
        {
            y=read(),z=read();
            modify_range(x,y,z);
        }
        else if(opt==2)
        {
            y=read();
            printf("%d\n",query_range(x,y));
        }
        else if(opt==3)
        {
            z=read();
            modify_son(x,z);
        }
        else
            printf("%d\n",query_son(x));
    }
    return 0;
}

P3379 【模板】最近公共祖先(LCA)

树剖也可以用来求解 lca,操作与区间修改查询很类似,只需每次选择链顶最深的节点往上跳,跳到一条链上时深度浅的那个点即为 lca。

当然,由于 lca 不涉及区间操作,所以不需要建线段树,也不要统计 dfs 序(开心)

事实证明,树剖解 lca 的常数比倍增小得多。

#include <cstdio>
#include <cctype>
#include <vector>

inline int read()
{...}

inline void swap(int &a,int &b)
{...}

const int maxn=500000+5;
int n,m,s;
int dep[maxn],fa[maxn],size[maxn],son[maxn],top[maxn];
std::vector<int> G[maxn];

void dfs1(int x,int father,int d)
{...}

void dfs2(int x,int topf)
{...}

int lca(int x,int y)
{
    while(top[x]!=top[y])
    {
        if(dep[top[x]]<dep[top[y]])
            swap(x,y);
        x=fa[top[x]];
    }
    if(dep[x]<dep[y])
        return x;
    else return y;
}

int main()
{...}

P3038 [USACO11DEC]Grass Planting G

边权转点权的例题,具体的没什么好讲的,把边映射到下面一个点就可以了。

主要是修改函数有一个地方需要注意:

void modify(int a,int b)
{
    while(top[a]!=top[b])
    {
        if(dep[top[a]]<dep[top[b]])
            swap(a,b);
        modify(1,n,id[top[a]],id[a],1);
        a=fa[top[a]];
    }
    if(dep[a]>dep[b])
        swap(a,b);
    modify(1,n,id[a]+1,id[b],1);//注意此处
    return;
}

在最后两个点跳到一条链上时,上面的点映射到的是上面的边,不在我们要处理的范围内,所以选择将其 dfs 序加一(链上 dfs 序连续),这样就可以避免处理到不该处理的边。

如果跳到同一条链上两点相同时,那没事了(划掉),因为进了线段树之后是弄不出东西的,所以无需担心这些问题。

最后修改日期:2020年10月1日

作者

留言

撰写回覆或留言

发布留言必须填写的电子邮件地址不会公开。