树链剖分学习笔记

树链剖分学习笔记

题型

当一道题在询问两点之间修改后的权值或者是两点之间边修改后的权值。这类题目往往我们一开始就会思考用线段树来维护,但是线段树无法维护一颗树上的链,所以我们需要来将树上的链剖分下来。

轻重边剖分

将树中的边分为两部分,轻边和重边,用$size[u]$来记录以$u$为根的子树的节点个数,之后令$v$为$u$的儿子中$size$最大的一个,那么我们就可以将$u$的边分为重边和轻边了(重边就是$(u.v)$)。

之后我们就可以得到如下性质

  • 如果$(u,v)$为轻边,那么$size[v] \leq size[u]/2$。因为如果大于的话,他就成为重边了。
  • 从根到某一点的路径上轻边的个数不会超过$logN$。假设从$root->v$,那么$size[v]>=1$,可以递推出$size[root]>=2^k$,其中$k$为根到点进过的点数。

实现

初始化操作

首先我们定义以下几个数组

  • $size[v]$表示以$v$为根的子树的节点数
  • $dep[v]$表示$v$的深度(根的深度为1)
  • $top[v]$表示所在重链的顶端节点
  • $fa[v]$表示父亲节点,$son[v]$表示重儿子节点
  • $w[v]$表示与父亲的连边

然后我们使用两个dfs来把数组确定下来。

第一个dfs求出fa,dep,size,top,w。

第二个dfs

  1. 对于循环到的$v$,当$son[v]$存在的时候,也就是非叶子节点,那么$top[son[v]] = top[v]$是显而易见的。在线段树中我们规定孩子节点的重边必须在父亲节点的后面,那么$w[son[v]]=totw+1$,其中$totw$表示线段树中加入的最后一条边的位置。之后进行递归dfs(son[v]);
  2. 对于$v$的轻孩子,那么他们没有身处重链所以$top[x]=x$。那么我们为了线段树好看一点也将他加入线段树。$w[x]=totw+1$。

经过两个dfs我们把所有的数组都给他确认了。

这代码量该有多大啊,对于常年只写70行就要debug很久的我来说。

更新操作

因为我们其实也是慢慢修改路径上的边的,所以我们先求个LCA。之后更新$u,v$到祖先节点。方法意会吧,或者看代码。

查询操作

跟更新操作很像,就是在过程中不再更新,而是求值。

例题

Aragorn’s Story

+1 更新节点的时候必须在id[x]更新

+1 大于小于没弄明白,在change函数中。

+1 update的时候以为是线段树直接从左边更新到右边,其实是在那个重边更新,所以是update(val,id[x],id[t1],1,totw,1);这样的操作。

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
#include<bits/stdc++.h>
using namespace std;
#define rep(i,a,n) for(int i=(a);i<(n);i++)
#define per(i,a,n) for(int i=(n-1);i>=(a);i--)
#define fi first
#define se second
#define lson l,mid,rt<<1
#define rson mid+1,r,rt<<1|1
void swap(int &a,int &b){
int temp = a;
a = b;
b = temp;
}
typedef pair <int,int> pII;
typedef long long ll;
const int INF = 0x3f3f3f3f;
//head
const int maxn = 5e4+10;
int size[maxn],dep[maxn],top[maxn],fa[maxn],id[maxn],son[maxn];
int head[maxn],w[maxn];
int n,cnt,totw,m;
struct edge{
int next,to;
}G[maxn<<1];
int find(int x){ return x==fa[x]?x:find(fa[x]);}
void addedge(int u,int v){
G[cnt].next = head[u];
G[cnt].to = v;
head[u] = cnt++;
}
void dfs1(int u,int f){
size[u] = 1;
for(int i=head[u];~i;i=G[i].next){
int v = G[i].to;
if(v==f) continue;
dep[v] = dep[u]+1;
fa[v] = u;
dfs1(v,u);
if(size[v] > size[son[u]]) son[u] = v;
size[u]+=size[v];
}
}
void dfs2(int u,int topu){
top[u] = topu;
id[u] = ++totw;
if(son[u]) dfs2(son[u],top[u]);
for(int i=head[u];~i;i=G[i].next){
int v = G[i].to;
if(v==fa[u] || v==son[u]) continue;
dfs2(v,v);
}
}
int data[maxn<<2],lazy[maxn<<2];
void pushdown(int rt){
if(lazy[rt]!=0){
data[rt<<1] += lazy[rt];
data[rt<<1|1] += lazy[rt];
lazy[rt<<1] += lazy[rt];
lazy[rt<<1|1] += lazy[rt];
lazy[rt] = 0;
}
}
void build(int l,int r,int rt){
lazy[rt] = 0;
if(l==r){
data[rt] = w[l];
return;
}
int mid = l+r>>1;
build(lson); build(rson);
}
int query(int pos,int l,int r,int rt){
if(l==r && l==pos) return data[rt];
int mid = l+r>>1;
pushdown(rt);
if(pos<=mid) return query(pos,lson);
else return query(pos,rson);
}
void update(int val,int L,int R,int l,int r,int rt){
if(L<=l && r<=R){
lazy[rt] += val;
data[rt] += val;
return;
}
pushdown(rt);
int mid = l+r>>1;
if(L<=mid) update(val,L,R,lson);
if(mid<R) update(val,L,R,rson);
}
void change(int u,int v,int val){
int t1=top[u],t2=top[v];
while(t1!=t2){
if(dep[t1]<dep[t2]){
swap(t1,t2);
swap(u,v);
}
update(val,id[t1],id[u],1,totw,1);
u = fa[t1];
t1 = top[u];
}
if(dep[u]>dep[v]) swap(u,v);
update(val,id[u],id[v],1,totw,1);
}
int val[maxn];
int p;
char op[20];
void init(){
cnt = totw = 0;
memset(head,-1,sizeof(head));
dep[1] = fa[1] = size[0] = 0;
memset(son,0,sizeof(son));
}
int main(){
#ifdef LOCAL
freopen("4.in","r",stdin);
#endif
while(~scanf("%d%d%d",&n,&m,&p)){
init();
rep(i,1,n+1) scanf("%d",val+i);
rep(i,0,m){
int u,v;scanf("%d%d",&u,&v);
addedge(u,v); addedge(v,u);
}
dfs1(1,0);
dfs2(1,1);
rep(i,1,n+1) w[id[i]] = val[i];
build(1,totw,1);
while(p--){
scanf("%s",op);
if(op[0]=='Q'){
int x;scanf("%d",&x);
printf("%d\n",query(id[x],1,totw,1));
}else{
int u,v,val;scanf("%d%d%d",&u,&v,&val);
if(op[0]=='D') val = -val;
change(u,v,val);
}
}
}
return 0;
}

个人鄙见:

树链剖分就是将树一部分分成区间修改,一部分分成单点修改,但是单点修改的复杂度控制在了$O(logN)$。

Reference:

https://blog.csdn.net/dyx404514/article/details/8718249