开始一直以为树剖是一个非常高大上的数据结构,怕学不会,学完之后发现树链剖分其实特别简单

问题概述

树链剖分(也叫轻重链剖分),是解决在树上进行区间修改、查询这一类问题的一个算法。 事实上,树链剖分就是由两遍dfs预处理+其他数据结构(如线段树、树状数组等)构成的。以洛谷P3384为例, 如果我们直接将每个节点按照dfs的顺序加入线段树中的话,每次修改或是查询都需要将u和v的路径之间所有的节点都处理一遍。 但是如果我们现将这棵树进行特殊的编号,使得在查询和修改时能够保证某一段连续的区间尽可能长,这样就可以降低我们的时间复杂度了。 事实上,将一棵树剖分为若干条链(每条链在线段树中是一段连续的区间),然后再利用线段树进行维护,这就是树链剖分。

一些定义

以节点u为例: size[u]:以u为根结点的子树的节点个数 重儿子(son[u]):u的子节点中size最大的子节点编号 轻儿子:u节点的其他子节点 重边:节点u与节点son[u]的边 重链:全部由重边组成的路径 轻边:节点u与其他子节点的边 deep[u]:节点u在树中的深度 fa[u]:节点u的父亲节点的编号 top[u]:节点u所在重链中深度最小的节点编号,也就是u所在重链的顶端 id[u]:节点u在线段树中的编号(视题目而定,若题目给的是边的权值及修改,那么则表示u的前驱边在线段树中的编号) real[u]:与id数组的映射(real[id[i]]=i) 关于这个它有两个重要的性质: (1)轻边(u,v)中,size(v)<=size(u/2) (2)从根到某一点的路径上,轻边和重边的个数均不超过logNlogN

算法流程

预处理

1、第一次dfs将每个节点的size、fa、deep、son都处理出来,找出每个节点的重儿子。这一部分比较简单,直接上代码:

1
2
3
4
5
6
7
8
9
10
11
12
inline void dfs1(int x){
size[x]=1;
for(int i=begin[x];i;i=next[i]){
int y=to[i];
if(fa[x]==y)continue;
fa[y]=x;
deep[y]=deep[x]+1;
dfs1(y);
if(size[y]>size[son[x]])son[x]=y;
size[x]+=size[y];
}
}

2、第二遍dfs求出每个节点的id、real、top。这里要强调的是,因为同一重链上的点必须在线段树中是连续的区间,那么如果对于节点u有重儿子(即不为叶子节点)的话,我们就必须先搜索他的重儿子。

1
2
3
4
5
6
7
8
9
10
11
12
int cnt=0;
inline void dfs2(int x,int now){
id[x]=++cnt;
real[id[x]]=x;
top[x]=now;
if(son[x])dfs2(son[x],now);
for(int i=begin[x];i;i=next[i]) {
int y=to[i];
if(fa[x]==y || son[x]==y)continue;
dfs2(y,y);
}
}

3、按照id数组建立线段树 预处理时间复杂度:O(NlogN)O(NlogN)

查询及修改

(一)求x到y路径节点值之和: 令t1=top[x],t2=top[y],则 1、如果t1==t2,则说明x和y在同一条重链上,设deep[x] < deep[y],那么只需要在线段数上查询(id[x],id[y])即可 2、如果t1!=t2,设deep[x]>=deep[y],我们先查询(id[t1],id[x]),然后x=fa[t1],直到t1==t2为止 代码如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
inline int find(int x,int y){
int sum=0,t1=top[x],t2=top[y];
while(t1!=t2){
if(deep[t1]<deep[t2]){swap(t1,t2);swap(x,y);}
sum+=query(1,1,n,id[t1],id[x]);
//cout<<x<<" "<<y<<" "<<sum<<endl;
sum%=Mod;
x=fa[t1];
t1=top[x];
}
if(deep[x]>deep[y])swap(x,y);
sum+=query(1,1,n,id[x],id[y]);
return sum%Mod;
}

修改的话,和查询的做法是一样的,只不过将query函数改为了update函数

1
2
3
4
5
6
7
8
9
10
11
inline void change(int x,int y,int z){
int t1=top[x],t2=top[y];
while(t1!=t2){
if(deep[t1]<deep[t2]){swap(t1,t2);swap(x,y);}
update(1,1,n,id[t1],id[x],z);
x=fa[t1];
t1=top[x];
}
if(deep[x]>deep[y])swap(x,y);
update(1,1,n,id[x],id[y],z);
}

(二)求以x为根节点的子树的节点值的和 因为我们是dfs进行的预处理,因此很容易发现x的子树的id一定是一段连续的区间,即

TeX parse error: Undefined control sequence \[

,修改同理 查询及修改复杂度Mlog2NMlog^2N

代码实现

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
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
#define begin Begin
#define next Next
#define size Size
#define find Find
#define deep Deep
#define change Change
using namespace std;
typedef long long LL;
const int maxn=5e5+5;
int begin[maxn],next[maxn],to[maxn],e;
int real[maxn],id[maxn];
int size[maxn],son[maxn],top[maxn],deep[maxn];
int fa[maxn];
int n,m,s;
LL Mod;
int a[maxn];
struct node{
int sum,mark;
}tree[maxn*4];
inline void add(int x,int y){
to[++e]=y;
next[e]=begin[x];
begin[x]=e;
}
inline void dfs1(int x){
size[x]=1;
for(int i=begin[x];i;i=next[i]){
int y=to[i];
if(fa[x]==y)continue;
fa[y]=x;
deep[y]=deep[x]+1;
dfs1(y);
if(size[y]>size[son[x]])son[x]=y;
size[x]+=size[y];
}
}
int cnt=0;
inline void dfs2(int x,int now){
id[x]=++cnt;
real[id[x]]=x;
top[x]=now;
if(son[x])dfs2(son[x],now);
for(int i=begin[x];i;i=next[i]) {
int y=to[i];
if(fa[x]==y || son[x]==y)continue;
dfs2(y,y);
}
}
inline void build(int root,int l,int r){
//cout<<root<<" "<<l<<" "<<r<<endl;
if(l==r){
tree[root].sum=a[real[l]];
return ;
}
int mid=(l+r)>>1;
build(root<<1,l,mid), build(root<<1|1,mid+1,r);
tree[root].sum=(tree[root<<1].sum+tree[root<<1|1].sum)%Mod;
}
inline void pushdown(int x,int l,int r,int mid){
if(tree[x].mark){
tree[x<<1].mark+=tree[x].mark;
tree[x<<1|1].mark+=tree[x].mark;
tree[x<<1].sum+=tree[x].mark*(mid-l+1);
tree[x<<1].sum%=Mod;
tree[x<<1|1].sum+=tree[x].mark*(r-mid);
tree[x<<1].sum%=Mod;
tree[x].mark=0;
}
return ;
}
inline void update(int root,int l,int r,int x,int y,int z){
int mid = (l + r) >> 1;
pushdown(root,l,r,mid);
if(x<=l && y>=r){
tree[root].mark+=z;
tree[root].sum+=(r-l+1)*z;
tree[root].sum%=Mod;
return ;
}
if(x<=mid)update(root<<1,l,mid,x,y,z);
if(y>mid)update(root<<1|1,mid+1,r,x,y,z);
tree[root].sum=(tree[root<<1].sum+tree[root<<1|1].sum)%Mod;
}
inline int query(int root,int l,int r,int x,int y){
int mid=(l+r)>>1;
pushdown(root,l,r,mid);
if(x<=l && y>=r)return tree[root].sum;
int ans=0;
if(x<=mid)ans+=query(root<<1,l,mid,x,y);
ans%=Mod;
if(y>mid)ans+=query(root<<1|1,mid+1,r,x,y);
return ans%Mod;
}
inline void change(int x,int y,int z){
int t1=top[x],t2=top[y];
while(t1!=t2){
if(deep[t1]<deep[t2]){swap(t1,t2);swap(x,y);}
update(1,1,n,id[t1],id[x],z);
x=fa[t1];
t1=top[x];
}
if(deep[x]>deep[y])swap(x,y);
update(1,1,n,id[x],id[y],z);
}
inline int find(int x,int y){
int sum=0,t1=top[x],t2=top[y];
while(t1!=t2){
if(deep[t1]<deep[t2]){swap(t1,t2);swap(x,y);}
sum+=query(1,1,n,id[t1],id[x]);
//cout<<x<<" "<<y<<" "<<sum<<endl;
sum%=Mod;
x=fa[t1];
t1=top[x];
}
if(deep[x]>deep[y])swap(x,y);
sum+=query(1,1,n,id[x],id[y]);
return sum%Mod;
}
int main(){
#ifndef ONLINE_JUDGE
freopen("a.in","r",stdin);
freopen("a.out","w",stdout);
#endif
scanf("%d%d%d%lld",&n,&m,&s,&Mod);
for(int i=1;i<=n;i++)scanf("%d",&a[i]);
int x,y,z,pd;
for(int i=1;i<n;i++){
scanf("%d%d",&x,&y);
add(x,y);add(y,x);
}
deep[s]=1;
dfs1(s);
top[s]=s;
dfs2(s,s);
build(1,1,n);
for(int i=1;i<=m;i++){
scanf("%d",&pd);
if(pd==1){
scanf("%d%d%d",&x,&y,&z);
change(x,y,z);
}
else if(pd==2){
scanf("%d%d",&x,&y);
printf("%d\n",find(x,y)%Mod);
}
else if(pd==3){
scanf("%d%d",&x,&z);
// cout<<id[x]<<" "<<id[x]+size[x]-1<<" "<<endl;
update(1,1,n,id[x],id[x]+size[x]-1,z);
}
else {
scanf("%d",&x);
printf("%d\n",query(1,1,n,id[x],id[x]+size[x]-1));
}
}
return 0;
}

几道例题

NOI2015 LuoguP2146 软件包管理器 传送门 ZJOI2008 LuoguP2590 树的统计 传送门