树链剖分从入门到入门

发布于 2021-04-19  253 次阅读


My Luogu Blog,Mathjax 炸了可以去那里QvQ

前置知识:$dfs$ 序、线段树。
此处的树链剖分均指轻重链剖分(长链剖分我也不会/kk)。

引入!

有时候我们会遇到这样一种题:

  1. 将树从 $x$ 到 $y$ 节点的最短路径上所有节点的值都加上 $val$ 。
  2. 求树从 $x$ 到 $y$ 节点的最短路径上所有节点的值之和。
  3. 将以 $x$ 为根的子树内所有节点值都加上 $val$ 。
  4. 求以 $x$ 为根的子树内所有节点值之和。
  5. 修改点 $x$ 的点权为 $val$。

诶,怎么做呢?

我们引入一个大宝贝解决树上问题的强力工具:树链剖分

树链剖分,顾名思义,就是将树分割成链,然后在链上进行操作处理

什么?你问我怎么处理?数据结构了解一下。

奇怪的概念!

重儿子:对于每个非叶子节点,它的儿子中 子树大小最大 的那一个儿子为该节点的重儿子。

轻儿子:对于每一个非叶子节点,它的儿子中非重儿子的其他儿子为轻儿子。

重边:连接两个重儿子的边叫做重边。

轻边:剩下非重边的边为轻边。

重链:重边首尾相连组成的链链叫重链。

对于叶子节点,若其为轻儿子,则有一条以自己为起点的长度为 1 的链。

每一条重链以轻儿子为起点。

剖剖剖!

名叫剖分,实际上不过是两遍 dfs 罢了。

dfs1:

第一遍dfs我们要维护的东西有:
$fa_x$ : 节点 $x$ 的父节点。
$dep_x$ : 节点 $x$ 的深度。
$siz_x$ : 节点 $x$ 为根的子树大小。
$son_x$ : 节点 $x$ 的重儿子编号。

代码:

inline void dfs1(int x,int father){
    siz[x]=1;
    fa[x]=father;
    dep[x]=dep[father]+1;
    for (int i=head[x];i;i=e[i].nxt){
        int v=e[i].vet;
        if (v==father) continue;
        dfs1(v,x);
        siz[x]=siz[x]+siz[v];
        if (siz[son[x]]<siz[v])
            son[x]=v;       //维护重儿子
    }
}

dfs2:

第二遍dfs,我们需要维护:
$top_x$ : 节点 $x$ 所在重链的顶端。
$newid_x$ : 节点 $x$ 在剖分后的新编号。
$anew_{cnt}$ : 剖分完后编号为 $cnt$ 的位置的值 (用于线段树的建树)。

代码:

inline void dfs2(int x,int Top){
    top[x]=Top;
    cnt++,newid[x]=cnt;
    a_new[cnt]=a[x];
    if (son[x]) dfs2(son[x],Top);       //优先遍历重儿子
    for (int i=head[x];i;i=e[i].nxt){
        int v=e[i].vet;
        if (v==fa[x]||v==son[x]) continue;
        dfs2(v,v);          //遍历轻儿子时,每个轻儿子都作为一条重链的顶端
    }
}

重要性质!

性质 1 :

因为在dfs时我们先遍历重儿子再遍历轻儿子,所以每一条重链的新编号是连续的

性质 2 :

因为是dfs,所以每一个子树的新编号也是连续的
(可以结合上面那张图理解一下)

性质 3 :

可以发现,当我们向下经过一条轻边时,所在子树的大小至少会除以二。
那么我们最多经过 $O(\log n)$ 条轻边。而轻链的链头上跟着重链,重链我们是直接跳到顶端的,所以从一个点向上走到根,进行轻重边切换的次数不超过 $O(\log n)$ 次。

诶现在怎么做呢?

  1. 将树从 $x$ 到 $y$ 节点的最短路径上所有节点的值都加上 $val$ 。
  2. 求树从 $x$ 到 $y$ 节点的最短路径上所有节点的值之和。
  3. 将以 $x$ 为根的子树内所有节点值都加上 $val$ 。
  4. 求以 $x$ 为根的子树内所有节点值之和。
  5. 修改点 $x$ 的点权为 $val$。

对于上面的操作 3 和 4 ,因为树剖的性质 2 ,我们可以发现问题已经转化到了序列上,可以直接用线段树进行维护(详情见代码)。

对于上面的操作 5 ,直接用线段树对 $newid_x$ 的位置进行单点修改就可以了。

重要的是上面的操作 1 和 2 。

对于操作 2 我们进行如下流程:
1. 令所在重链顶端节点的深度较深的点为 $x$,利用树剖的性质 1 ,可以发现这是一段连续区间,用数据结构(线段树)维护答案。
2. 令 $x$ 跳到 所在重链顶端节点的父节点。
3. 重复操作 1 和 2 直到 $x$ 和 $y$ 在同一条重链上。
4. 此时同样根据性质 1 , $x$ 到 $y$ 是一段连续区间,统计答案即可。

操作 1 同理,不过是把线段树的区间查询改成了区间修改而已。

代码(以操作 2 为例):

inline ll ex_query(int x,int y){
    ll ans=0;
    while (top[x]!=top[y]){
        if (dep[top[x]]<dep[top[y]]) swap(x,y);     //令 x 为重链顶端节点较深的节点
        (ans+=(query(1,newid[top[x]],newid[x])))%=Mod;      //统计答案
        x=fa[top[x]];       // x 上调到重链顶端节点的父节点
    }
    if (dep[x]>dep[y]) swap(x,y);       //此时 x 和 y 在同一段区间上,令 x 为较深的点
    (ans+=query(1,newid[x],newid[y]))%=Mod;     //统计答案
    return ans;
}

至于线段树的代码我就不放了,不熟悉的同学建议去这个地方复习一下。

另外,在建树时有一个坑点,在叶子节点赋初值时赋的不是 $a_l$ ,是 $anew_l$ 嗷!

inline void build(int id,int l,int r){
    tree[id].l=l,tree[id].r=r;
    if (l==r){
        tree[id].sum=a_new[l];      //就是这里!
        return;
    }
    int mid=(l+r)>>1;
    build(lid,l,mid);
    build(rid,mid+1,r);
    tree[id].sum=tree[lid].sum+tree[rid].sum;
}

啊,时间复杂度显然是建树 $O(n \log n)$ ,而对于单次查询,我们考虑轻重边都不超过 $O(\log n)$ 条(性质 3 ),而单次线段树处理是 $O(\log n)$ 的,所以单次查询时间复杂度为 $O(\log^2 n)$ 。

模板题!

就是这道题了:Luogu3384 轻重链剖分
就是之前的操作 1 到 4 ,没什么好多说的,直接给代码了。

#include<bits/stdc++.h>
#define ll long long
#define lid (id<<1)
#define rid (id<<1|1)
using namespace std;
const int N=100005;

struct Edge{
    int vet,nxt;
}e[N<<1];

struct Node{
    int l,r;
    ll lazy,sum;
}tree[N<<2];

int n,Q,root,Mod,edge=0,cnt=0,head[N];
int dep[N],fa[N],top[N],siz[N],son[N];
int a[N],a_new[N],newid[N];

inline int read(){
    int x=0,f=1; char ch=getchar();
    while (!isdigit(ch)) { if (ch=='-') f=-1; ch=getchar(); }
    while (isdigit(ch)) { x=x*10+ch-'0'; ch=getchar(); }
    return x*f;
}

inline void addedge(int x,int y){
    e[++edge].vet=y;
    e[edge].nxt=head[x];
    head[x]=edge;
}

inline void dfs1(int x,int father){
    siz[x]=1;
    fa[x]=father;
    dep[x]=dep[father]+1;
    for (int i=head[x];i;i=e[i].nxt){
        int v=e[i].vet;
        if (v==father) continue;
        dfs1(v,x);
        siz[x]+=siz[v];
        if (siz[v]>siz[son[x]])
            son[x]=v;
    }
}

inline void dfs2(int x,int Top){
    top[x]=Top;
    newid[x]=++cnt;
    a_new[cnt]=a[x];
    if (son[x]) dfs2(son[x],Top);
    for (int i=head[x];i;i=e[i].nxt){
        int v=e[i].vet;
        if (v==fa[x] || v==son[x]) continue;
        dfs2(v,v);
    }
}

//下面是线段树模板

inline void build(int id,int l,int r){
    tree[id].l=l,tree[id].r=r;
    if (l==r){
        tree[id].sum=a_new[l];
        return;
    }
    int mid=(l+r)>>1;
    build(lid,l,mid);
    build(rid,mid+1,r);
    tree[id].sum=(tree[lid].sum+tree[rid].sum)%Mod;
}

inline void pushdown(int id){
    if (tree[id].lazy && tree[id].l!=tree[id].r){
        (tree[lid].lazy+=tree[id].lazy)%=Mod;
        (tree[rid].lazy+=tree[id].lazy)%=Mod;
        (tree[lid].sum+=(tree[id].lazy*(tree[lid].r-tree[lid].l+1)%Mod))%=Mod;
        (tree[rid].sum+=(tree[id].lazy*(tree[rid].r-tree[rid].l+1)%Mod))%=Mod;
        tree[id].lazy=0;
    }
}

inline void change(int id,int l,int r,int val){
    if (tree[id].l>=l && tree[id].r<=r){
        (tree[id].lazy+=val)%=Mod;
        (tree[id].sum+=val*(tree[id].r-tree[id].l+1)%Mod)%Mod;
        return;
    }
    pushdown(id);
    int mid=(tree[id].l+tree[id].r)>>1;
    if (r<=mid) change(lid,l,r,val);
    else if (l>mid) change(rid,l,r,val);
    else change(lid,l,mid,val),change(rid,mid+1,r,val);
    tree[id].sum=(tree[lid].sum+tree[rid].sum)%Mod;
}

inline ll query(int id,int l,int r){
    if (tree[id].l>=l && tree[id].r<=r)
        return tree[id].sum%Mod;
    pushdown(id);
    int mid=(tree[id].l+tree[id].r)>>1;
    if (r<=mid) return query(lid,l,r)%Mod;
    else if (l>mid) return query(rid,l,r)%Mod;
    else return (query(lid,l,mid)+query(rid,mid+1,r))%Mod;
}

//上面是线段树模板

inline void ex_change(int x,int y,int val){
    while (top[x]!=top[y]){
        if (dep[top[x]]<dep[top[y]]) swap(x,y);
        change(1,newid[top[x]],newid[x],val);
        x=fa[top[x]];
    }
    if (dep[x]>dep[y]) swap(x,y);
    change(1,newid[x],newid[y],val);
}

inline ll ex_query(int x,int y){
    ll ans=0;
    while (top[x]!=top[y]){
        if (dep[top[x]]<dep[top[y]]) swap(x,y);
        (ans+=(query(1,newid[top[x]],newid[x])))%=Mod;
        x=fa[top[x]];
    }
    if (dep[x]>dep[y]) swap(x,y);
    (ans+=query(1,newid[x],newid[y]))%=Mod;
    return ans;
}

int main(){
    //freopen("tree-chain-partition.in","r",stdin);
    //freopen("tree-chain-partition.out","w",stdout);
    n=read(),Q=read(),root=read(),Mod=read();
    for (int i=1;i<=n;++i) a[i]=read();
    for (int i=1;i<=n-1;++i){
        int x=read(),y=read();
        addedge(x,y);
        addedge(y,x);
    }
    dep[root]=1,dfs1(root,0);
    cnt=0,dfs2(root,root);
    // for (int i=1;i<=n;++i)
    //  printf("i=%d fa=%d dep=%d siz=%d son=%dn",i,fa[i],dep[i],siz[i],son[i]);
    build(1,1,n);
    for (int i=1;i<=Q;++i){
        int opt=read();
        if (opt==1){
            int x=read(),y=read(),val=read();
            ex_change(x,y,val);
        }
        else if (opt==2){
            int x=read(),y=read();
            printf("%lld\n",ex_query(x,y));
        }
        else if (opt==3){
            int x=read(),val=read();
            change(1,newid[x],newid[x]+siz[x]-1,val);
        }
        else if (opt==4){
            int x=read();
            printf("%lld\n",query(1,newid[x],newid[x]+siz[x]-1));
        }
    }
    return 0;
}

其他应用!

  1. [ZJOI2008] 树的统计

给定一颗 $n$ 个点的点带权的树,$q$ 次操作,为下列的一种:
I. CHANGE u t : 把结点 $u$ 的权值改为 $t$。
II. QMAX u v: 询问从点 $u$ 到点 $v$ 的路径上的节点的最大权值。
III. QSUM u v: 询问从点 $u$ 到点 $v$ 的路径上的节点的权值和。
$ 1 \le n \le 3 \times 10^4 ,0 \le q \le 2 \times 10^5$,点权 $w \in [ -3 \times 10^4,3 \times 10^4]$

几乎是裸题吧。单点修改的时候要修改的位置应该是 $newid_x$ 而不是 $x$ ,然后记得在 $QMax$ 时结果的初值要赋 $-inf$ (题目中的值是有负数的)。

我的写法是把 $QMax$ 和 $QSum$ 放一起,加个参数 $Opt$ ,然后就导致代码变得极丑。。。

代码就挂个链接吧,树剖的代码动不动就一两百行,再加上我的码风不行,全部挂上来会导致阅读体验极差。。

Code

  1. [SDOI2011] 染色

给定一棵 $n$ 个节点的无根树,初始节点 $i$的 权值为 $w_i$ ,有 $m$ 个操作,操作分为两种:
I. C x y c : 将节点 $x$ 到节点 $y$ 的路径上的所有点(包括 $x$ 和 $y$)都染成颜色 $c$ 。
II. Q x y : 询问节点 $x$ 到节点 $y$ 的路径上的颜色段数量。
Ps:极长连续相同颜色组成的一段区间为一段颜色段。
$1 \leq n, m \leq 10^5,1 \leq w_i, c \leq 10^9$

显然要把树上问题转化成序列上的问题。

考虑如何用线段树维护这个问题。只记颜色段数肯定是不够的:我们考虑两段子区间合并时,如果左区间的最右边和右区间的最左边可以拼起来,那么答案显然不应该是两个子区间颜色段的和,而应该是这个和 -1 。所以我们可以多记录最左边的颜色和最右边的颜色,如果出现上述可以合并的情况就直接把和 -1 就可以了。

然后您按照这么写就会发现样例都过不去。。。

您会发现这样做好像漏了一种情况:考虑下图所示的情况。

那么当 $Now.Right=Last.Left$ 时显然这两段要合并。
所以我们记录一下上次做出来的值,进行判断即可。记得在程序中 $swap(x,y)$ 时顺便 $Swap$ 一下这个记录值,保证对应上了即可。

同理,当 $x$ 和 $y$ 跳到同一条重链上时我们要对这段区间的两头分别进行判断,不明白的可以画个图仔细理解一下。

Code

  1. [SDOI2014]旅行

给定 $n$ 座城市和 $n-1$ 条道路的一棵树,每个城市有一种信仰和一个权值,要求支持下列事件:
I. CC x c:城市x的居民全体改信了c教;
II. CW x w:城市x的评级调整为w;
III. QS x y:一位旅行者从城市x出发,到城市y,并记下了途中留宿过的城市的评级总和;
IV. QM x y:一位旅行者从城市x出发,到城市y,并记下了途中留宿过的城市的评级最大值。
输出所有旅行者记录下的值。
$1 \le n,m \le 10^5 , 1 \leq w_i, c \leq 10^9$

显然还是要利用树剖把树上问题转化到区间上。这题的难点显然在于信仰,怎么解决呢?

一种显然的想法是开 $n$ 棵线段树。但是这样显然会 MLE 。

怎么办呢?考虑到总结点只有 $n$ 个,我们考虑用动态开点线段树。开一个 $root$ 数组记录每一种颜色在线段树内的根,对于每个节点再记录一下左右儿子,此时对于一种颜色的操作可以直接从这个根开始往下做,与正常线段树无异。

动态开点线段树不会的建议去学一下再看。
我的这篇博客里也提了一下动态开点线段树。

这里直接放一个动态开点线段树的 $update$:

inline void update(int &id,int l,int r,int x,int val){ 
    //这里id是引用,在改变id的同时,
    //它父亲的lson和rson也会改变(见下面的递归调用)
    if (!id) id=++cnt;
    tree[id].l=l,tree[id].r=r;
    if (l==r){
        tree[id].sum=val;
        return;
    }
    int mid=(l+r)>>1;
    if (x<=mid) update(lid,l,mid,x,val);
    else update(rid,mid+1,r,x,val);
    tree[id].sum=tree[lid].sum+tree[rid].sum;
}
//本题中使用时直接调用 update(root[c[i].col],1,n,newid[i],c[i].val) 即可

2 3 4操作几乎是模板。我们来看 1 操作。修改颜色显然不能直接套个单点模板上去。我们考虑把它拆分成删除和添加两部分。也就是先把要修改的节点 $x$ 在它原来的 $root[oldcol]$ 为根的子树中删掉,再加到 $root[newcol]$ 为根的子树里。

其他的就没什么好讲的了。细节很多,善用调试。

Code

  1. 月下毛景树

“毛景树”上有 $n$ 个节点和 $n-1$ 条树枝,但节点上没有果实,果实长在树枝上。
要求支持下列操作:
I. Change k w:将第 $k$ 条树枝上果实的个数改变为 $w$ 个。
II. Cover u v w:将节点 $u$ 与节点 $v$ 之间的树枝上果实的个数都改变为w个。
III. Add u v w:将节点 $u$ 与节点 $v$ 之间的树枝上果实的个数都增加w个。
IV. Max u v:询问节点 $u$ 与节点 $v$ 之间树枝上毛毛果个数最多有多少个。
$1 \le n \le 10^5$,操作+询问数目不超过 $10^5$ 。
保证在任意时刻,所有树枝上毛毛果的个数都不会超过 $10^9$ 个。

树剖边权转点权的模板题。

我们考虑到一个点可以有多个儿子,但是只能有一个父亲,那么如果把一条边的权值推到深度较浅的节点,会出现多条边挤在一起的情况,所以我们把一条边的权值推到深度较深的节点

此时在维护 $x$ $y$ 两点间链的路径时我们要注意:它们的LCA表示的是LCA到父亲那条边,是不在要修改的范围内的。所以当跳到一条重链上的时候我们调用的是query/change(1,newid[x]+1,newid[y]) ,即区间的左端点是 $newid[x]+1$ 而不是 $newid[x]$ 。

另外就是线段树维护区间颜色最大值。对于区间覆盖、区间增加和单点修改只需要维护覆盖值的懒标记和加上值的懒标记。前者的优先级是大于后者的,具体实现可以看代码。

Code

  1. [LNOI2014]LCA

给出一个 $n$ 个节点的有根树(编号为 $0$ 到 $n−1$ ,根节点为 $0$ )。 一个点的深度定义为这个节点到根的距离 $+1$。
有 $q$ 次询问,每次询问给出 $l , r , z$ ,求 $sum_{i=l}^r dep[LCA(i,z)]$ 。
$1 \le n,q \le 50000$

一道很有意思的题。我们考虑 $dep_x$ 的意义是 $x$ 到根节点的节点个数。而且从 $LCA(l,z)$ 到 $LCA(r,z)$ 显然都在 $z$ 到根节点的路径上。那么我们考虑对于一个 $dep_x$ 的贡献,我们把它转化为从根节点到 $x$ 的路径上的记录值全部 $+1$ 。

诶这样是不是就可以通过本题了呢?

当然。
不是。

考虑对于每次询问,都从 $l$ 到 $r$ 一个一个插入,单次复杂度 $O(n \log ^2 n)$ ,再加上 $q$ 次查询,显然不太行,甚至比暴力快不了多少

那怎么办呢?

由于区间 $[l,r]$ 的答案显然可以拆分成 $[1,r]$ 减去 $[1,l-1]$ 的答案,所以我们考虑把询问离线,利用差分把区间裂成两个。

有什么用呢?
我们发现此时把询问拆成两个,按照询问的位置排序。每次把指针移动到当前询问的位置,然后在对应的原询问编号上加上答案就可以了。

具体可以看部分代码比较好理解。

    int tot=0;
    for (int i=1;i<=m;++i){
        int l,r,x;
        readint(l),++l; readint(r),++r; readint(x),++x;
        q[++tot]=(Question){l-1,x,i,-1};
        q[++tot]=(Question){r,x,i,1};
        //把询问拆成两个
    }
    sort(q+1,q+tot+1,mycmp);
    int Now=0;
    for (int i=1;i<=tot;++i){
        while (Now<q[i].pos) ex_change(1,++Now,1);      //移动指针到当前位置
        ans[q[i].id]+=q[i].tag*ex_query(1,q[i].x);
        //统计答案
    }
    for (int i=1;i<=m;++i){
        if (ans[i]<0) ans[i]+=Mod;      //因为有取模,可能出现负数的情况,直接加上就好了。
        printint(ans[i]),putc('\n');
    }

由于询问的位置是有序,每个节点只会被插入一次,总时间复杂度是 $O(n \log^2 n)$ 级别的(这里认为 $n,q$ 同阶)。

完整版的Code here

感谢!

部分关于概念的内容改编自OI-wiki


我们无法选择过去,但我们可以改变未来。