树链剖分学习笔记

本文最后更新于 2025年5月17日 下午

注:本文结合了一些 Drest 和 Targanzqq 的笔记和讲解内容,在此感激不尽.

0 一些前置芝士

  • 线段树

1 什么是树链剖分

在大多数情况下,我们所说的"树链剖分"通常都是指的重链剖分.

众所周知,在处理序列问题上,我们有很多种方法,比如线段树,树状数组,平衡树…

那么,如何处理树上问题呢?

一种思路是将一棵树拍成一个序列(如dfs序),然后对序列进行操作.而树链剖分也运用了类似这样的思想.

树链剖分的大体思路就是把一棵树剖成若干条重链,然后根据性质用线段树(也可以用其他数据结构,如树状数组)维护.

2 一些定义

  • 重儿子:一个结点的所有儿子中子树结点最多(子树大小最大)的儿子

  • 轻儿子:与重儿子相对而言,一个结点所有儿子除了重儿子之外的都是轻儿子

  • 重边:一个结点与其重儿子所连的边

  • 重链:由若干条重边连接起来的链

同时,单个的轻儿子也可算作一条重链

如图,蓝色的节点就是重儿子.

图中有4条重链,分别是1->2->4->8 , 3->6 ,7和5.

3 一些性质

树链剖分的实现十分依赖重链的性质,因为这牵扯到复杂度分析.

树链剖分有两个最常用的性质,分别是:

  1. 每条重链的顶端一定是一个轻儿子

  2. 每个轻儿子一定是一条重链的顶端

  3. 树上任意两点之间的唯一确定路径一定可以被分为不超过 log⁡n\log n 条重链.

下面分别证明这两个性质:

  1. 假设存在一条重链,使得其顶端为重儿子,那么这个重儿子必然还有一条连向其父亲节点的重边,因此就不是重链的顶端,与题设矛盾,所以每条重链的顶端一定是一个轻儿子.

  2. 假设存在一个轻儿子,使得这个轻儿子不是一条重链的顶端,那么其父亲节点一定有一条重链连向这个轻儿子,所以这个节点是重儿子,与题设矛盾,所以一个轻儿子一定是一条重链的顶端.

  3. 待证

在确定每个点的重儿子之后,我们对整棵树进行遍历,先遍历每个节点的重儿子,再遍历每个节点的轻儿子.

然后,我们根据遍历的顺却重新确定每个节点的编号,如下图.

然后,我们惊奇的发现了这个编号的两个性质:

  1. 任意一条重链上的所有节点编号是连续的

  2. 任意一个子树内的所有节点编号是连续的

由于这两个性质,我们可以将这棵树按照这个编号拍成一个序列,然后用数据结构维护这个序列,使得实现我们想要的功能.

4 如何实现

注: 下面的所有内容均以树链剖分模板题 P3384 为例

上面的部分都是理论基础,下面我们来讲讲如何代码实现.

大体的思路是先处理出来这棵树的各种信息,然后转化为序列再用数据结构(这里采用线段树)维护.

4.0 线段树

线段树代码如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
//写的很难看的线段树
int tree[N*4];
int tag[N*4];
void pushup(int u){
    tree[u]=tree[u*2]+tree[u*2+1];
}
void build(int now,int l,int r){
    if(l==r){tree[now]=val[l];return;}
    int mid=l+r>>1;
    build(now*2,l,mid);
    build(now*2+1,mid+1,r);
    pushup(now);
}

void change(int x,int len,int val){
    tag[x]+=val;
    tree[x]+=len*val;
}
void pushdown(int x,int l,int r){
    int mid=(l+r)>>1;
    change(x*2,mid-l+1,tag[x]);
    change(x*2+1,r-mid,tag[x]);
    tag[x]=0;
}

void update(int x,int left,int right,int l,int r,int val){//线段树修改
    if(l<=left&&right<=r){      
        change(x,right-left+1,val);
    }else if(!(r<left||right<l)){
        int mid=(left+right)>>1;
        pushdown(x,left,right);
        update(x*2,left,mid,l,r,val);
        update(x*2+1,mid+1,right,l,r,val);
        pushup(x);
    }
}
int query(int x,int left,int right,int l,int r){//线段树查询
    if(l<=left&&right<=r){
        return tree[x];
    }else if(!(r<left||l>right)){
        int mid=(left+right)>>1;
        pushdown(x,left,right);
        return query(x*2,left,mid,l,r)+query(x*2+1,mid+1,right,l,r);
    }else return 0; 
}

4.1 预处理信息

首先,我们需要通过两次dfs来处理下列信息:

  1. deepideep_i :表示i在树中的深度

  2. sizisiz_i :表示i的子树大小

  3. faifa_i :表示i的父亲节点

  4. sonison_i :表示i的重儿子

  5. topitop_i :表示i所在重链的顶端

  6. idiid_i :表示i节点的新编号

  7. valival_i :表示重新编号后的i的节点的值,令 viv_i 表示重新编号前的i的节点的值,则有 vali=vidival_i=v_{id_i}

第一次dfs处理前4个信息,可以直接通过记录 dfs(now,fa)dfs(now,fa) 来处理这4个信息.

1
2
3
4
5
6
7
8
9
10
11
void dfs0(int now,int father){
    deep[now]=deep[father]+1;
    fa[now]=father;
    siz[now]=1;
    for(auto &i:g[now]){
        if(i==father)continue;
        dfs0(i,now);
        siz[now]+=siz[i];
        if(siz[i]>siz[son[now]])son[now]=i;
    }
}

第二次dfs处理后3个信息,我们可以通过记录当前点和当前点所在重链的顶端来进行dfs.

1
2
3
4
5
6
7
8
9
10
11
12
13
void dfs1(int now,int tp){
    top[now]=tp;
    id[now]=++cnt,val[id[now]]=v[now];//分配新的编号并且记录值
    if(son[now]==0){
        return;//若无重儿子则返回
    }
    dfs1(son[now],tp);//先遍历重儿子
    for(auto &i:g[now]){
        if(i==fa[now]||i==son[now])continue;
        dfs1(i,i);//再遍历轻儿子
        //由于轻儿子一定是一个重链的顶端,所以遍历轻儿子时,其所在重链顶端就是它本身.
    }
}

处理完信息后,我们就可以开始考虑如何维护这四种操作:

  • 1 x y z，表示将树从 xx 到 yy 结点最短路径上所有节点的值都加上 zz。

  • 2 x y，表示求树从 xx 到 yy 结点最短路径上所有节点的值之和。

  • 3 x z，表示将以 xx 为根节点的子树内所有节点值都加上 zz。

  • 4 x 表示求以 xx 为根节点的子树内所有节点值之和

也就是维护路径和,路径修改,子树和与子树修改.

4.2 路径操作

以查询操作为例,当 u,vu,v 两点不在一条重链上时,我们要将两个点都跳到一条重链上,并且由于每条重链上的点的编号都是连续的,我们可以直接记录每条跳过的重链的值的和.

当两个点到一条重链上时,可以直接记录两点之间的值的和.

修改操作同理,将代码中的记录操作改成修改操作即可.

示例代码如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
int querypath(int u,int v){//路径查询
    int ret=0;
    while(top[u]!=top[v]){
        if(deep[top[u]]<deep[top[v]])swap(u,v);
        ret=ret+query(1,1,cnt,id[top[u]],id[u]);
        u=fa[top[u]]; 
    }
    if(deep[u]<deep[v])swap(u,v);
    ret=ret+query(1,1,cnt,id[v],id[u]);
    return ret;
}
void updatepath(int u,int v,int k){//路径修改
    while(top[u]!=top[v]){
        if(deep[top[u]]<deep[top[v]])swap(u,v);
        update(1,1,cnt,id[top[u]],id[u],k);
        u=fa[top[u]];
    }
    if(deep[u]<deep[v])swap(u,v);
    update(1,1,cnt,id[v],id[u],k);
}

4.3 子树操作

子树操作相对而言简单很多.

由于每个子树在序列中都是连续的,长度为 sizi−1siz_i-1的一段,我们可以直接进行操作.

代码如下:

1
2
3
4
5
6
int querytree(int u){
    return query(1,1,cnt,id[u],id[u]+siz[u]-1);
}
void updatetree(int u,int k){
    update(1,1,cnt,id[u],id[u]+siz[u]-1,k);
}

4.4 主函数部分:

主函数就非常简单了.

代码如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
signed main(){
    n=read(),m=read(),r=read(),p=read();
    for(int i=1;i<=n;++i){v[i]=read();}
    for(int i=1;i<n;++i){
        int u=read(),v=read();
        g[u].push_back(v);
        g[v].push_back(u);
    }
    dfs0(r,0);
    dfs1(r,r);
    build(1,1,n);
    while(m--){
        int op=read();
        if(op==1){
            int x=read(),y=read(),z=read();
            updatepath(x,y,z);
        }else if(op==2){
            int x=read(),y=read();  
            printf("%lld\n",querypath(x,y)%p);
        }else if(op==3){
            int x=read(),z=read();
            updatetree(x,z);
        }else{
            int x=read();
            printf("%lld\n",querytree(x)%p);
        }
    }
}

4.5 完整代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
#include <bits/stdc++.h>
using namespace std;
#define int long long
int read(){
    int f=1,s=0;char c=getchar();
    while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}
    while(c>='0'&&c<='9'){s=(s<<1)+(s<<3)+(c-'0');c=getchar();}
    return f*s;
}
const int N=114514;
int v[N],deep[N],son[N],siz[N],fa[N],top[N],id[N],val[N],cnt;
vector<int> g[N];
int n,m,r,p;

void dfs0(int now,int father){
    deep[now]=deep[father]+1;
    fa[now]=father;
    siz[now]=1;
    for(auto &i:g[now]){
        if(i==father)continue;
        dfs0(i,now);
        siz[now]+=siz[i];
        if(siz[i]>siz[son[now]])son[now]=i;
    }
}
void dfs1(int now,int tp){
    top[now]=tp,id[now]=++cnt,val[id[now]]=v[now];
    if(son[now]==0){
        return;
    }
    dfs1(son[now],tp);
    for(auto &i:g[now]){
        if(i==fa[now]||i==son[now])continue;
        dfs1(i,i);
    }
}

int tree[N*4];
int tag[N*4];
void pushup(int u){
    tree[u]=tree[u*2]+tree[u*2+1];
}
void build(int now,int l,int r){
    if(l==r){tree[now]=val[l];return;}
    int mid=l+r>>1;
    build(now*2,l,mid);
    build(now*2+1,mid+1,r);
    pushup(now);
}

void change(int x,int len,int val){
    tag[x]+=val;
    tree[x]+=len*val;
}
void pushdown(int x,int l,int r){
    int mid=(l+r)>>1;
    change(x*2,mid-l+1,tag[x]);
    change(x*2+1,r-mid,tag[x]);
    tag[x]=0;
}

void update(int x,int left,int right,int l,int r,int val){
    if(l<=left&&right<=r){      
        change(x,right-left+1,val);
    }else if(!(r<left||right<l)){
        int mid=(left+right)>>1;
        pushdown(x,left,right);
        update(x*2,left,mid,l,r,val);
        update(x*2+1,mid+1,right,l,r,val);
        pushup(x);
    }
}
int query(int x,int left,int right,int l,int r){
    if(l<=left&&right<=r){
        return tree[x];
    }else if(!(r<left||l>right)){
        int mid=(left+right)>>1;
        pushdown(x,left,right);
        return query(x*2,left,mid,l,r)+query(x*2+1,mid+1,right,l,r);
    }else return 0; 
}

int querypath(int u,int v){
    int ret=0;
    while(top[u]!=top[v]){
        if(deep[top[u]]<deep[top[v]])swap(u,v);
        ret=ret+query(1,1,cnt,id[top[u]],id[u]);
        u=fa[top[u]]; 
    }
    if(deep[u]<deep[v])swap(u,v);
    ret=ret+query(1,1,cnt,id[v],id[u]);
    return ret;
}
int querytree(int u){
    return query(1,1,cnt,id[u],id[u]+siz[u]-1);
}
void updatepath(int u,int v,int k){
    while(top[u]!=top[v]){
        if(deep[top[u]]<deep[top[v]])swap(u,v);
        update(1,1,cnt,id[top[u]],id[u],k);
        u=fa[top[u]];
    }
    if(deep[u]<deep[v])swap(u,v);
    update(1,1,cnt,id[v],id[u],k);
}
void updatetree(int u,int k){
    update(1,1,cnt,id[u],id[u]+siz[u]-1,k);
}

signed main(){
    n=read(),m=read(),r=read(),p=read();
    for(int i=1;i<=n;++i){v[i]=read();}
    for(int i=1;i<n;++i){
        int u=read(),v=read();
        g[u].push_back(v);
        g[v].push_back(u);
    }
    dfs0(r,0);
    dfs1(r,r);
    build(1,1,n);
    while(m--){
        int op=read();
        if(op==1){
            int x=read(),y=read(),z=read();
            updatepath(x,y,z);
        }else if(op==2){
            int x=read(),y=read();  
            printf("%lld\n",querypath(x,y)%p);
        }else if(op==3){
            int x=read(),z=read();
            updatetree(x,z);
        }else{
            int x=read();
            printf("%lld\n",querytree(x)%p);
        }
    }
}

4.6 时间复杂度分析

前面的两次dfs,由于是每个点遍历一次,所以时间复杂度 O(n)O(n)

每次对于进行路径的操作,在两个点跳到同一条重链上的过程中,由于重链的性质,一定不会跳超过 log⁡n\log n 次.又因为每次跳的时候又会进行一次线段树的操作,时间复杂度 O(log⁡n)O(\log n),所以每次进行路径操作的时间复杂度是 O(log⁡2n)O(\log^2 n).

对于每次的子树操作,只需要进行一次线段树的操作,所以时间复杂度 O(log⁡n)O(\log n)

由于需要进行 mm 次操作,所以总时间复杂度为 O(mlog⁡2n)O(m \log^2 n)

5 后记

好长。

笔记
#数据结构
树链剖分学习笔记
http://ljhljh1102,github.io/2024/07/13/树链剖分学习笔记/
作者
1102
发布于
2024年7月13日
许可协议