【算法笔记】树链剖分（轻重链剖分）

是什么

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

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

• 将 x 到 y 的路径上的点权全部加上 z
• 查询 x 到 y 的路径上的点权之和
• 将以 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 序连续），这样就可以避免处理到不该处理的边。

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