树链剖分 --不一样的详解

欢迎转载,转载请注明来自 bestsort的博客 并保留该超链接

算了算自己大大小小也看了不下十几篇关于树链剖分的博客了吧,但是总感觉差强人意,基本上都是一上来就告诉读者我们来先背几个概念,然后就是 轻儿子重儿子重边重链 什么的一股脑全堆上来.但是个人感觉这种方式对初学者并不友好! 笔者不才,打算自己根据对树链剖分的理解重新写一篇真正适合入门的详解


这里,笔者打算以 What-How-Why(黄金圈法则) 的方式进行讲解.先知道树链剖分是什么,它有什么用,再去了解它怎么实现,具体原理是什么

What

树链剖分是什么

树链剖分就是将树分割成多条链,然后利用数据结构(线段树、树状数组等)来维护这些链。

实际上,这些链是一条条平躺着放在数组里面的

How

映射的规则

上文中说过树链剖分是把树分割成多条链,并将其映射到一维数组

当然分割是要讲道理滴!自然要遵循某些规则

这里的规则很简单,那就是

在一维区间中,对于任意树上结点 x, 则 x 的所有子孙结点都在以 x 为起点的一段连续区间内(当然,树链还有一些其他的约束条件,我们放到后面再说)

很难理解?

比如说 我有下图这颗树

)

我们可以构造出下面这些区间,都满足上面的规则.(注意是任意结点 x 都满足规则)

1
2
3
4
5
6
7
8
#分别对应 [ABDCEF],[BD],[CEF]
ABDCEF

#[ACEFBD],[CEF],[BD]
ACEFBD

#[ACFEBD],[CFE],[BD]
ACFEBD

也就是说映射到最后的结果是:对于任意节点 x, x 和它的子树在区间内一定连续的


对于这个规则,我们不难想到,其实就是一个 DFS 的事情(想不通的可以看一下二叉树的前中后序遍历出来的结果).

Ok, 现在我们知道了,要用 DFS 将树映射成一维区间.可是遍历顺序有没有影响?

有的!

而正是因为分割规则的不同,才有长链剖分重链剖分这两种说法,本文只讲重链剖分.当然不是说长链剖分就没用,两者在不同的场合都有各自的优势,这里不赘述了

回到上文,遍历顺序是对最终的复杂度有影响的.这里举一个具体的例子,如下图:


有点懒,不想写了….具体的待补充


题目链接 先放代码占坑,过几天有空再写

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
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
    
#include <bits/stdc++.h>

using namespace std;
#define mem(a, b) memset(a, b, sizeof a)
#define IN freopen("in.txt", "r", stdin)
#define DEBUG(a) cout << (a) << endl

typedef long long ll;
int dir8[8][2] = { {1, 0}, {0, 1}, {-1, 0}, {0, -1}, {1, 1}, {1, -1}, {-1, 1}, {-1, -1}};
int dir4[4][2] = {1, 0, 0, 1, -1, 0, 0, -1};
const int INF = 0x3f3f3f3f;
int mod = 1e9 + 7;
const int maxn = 1e6 + 10;

struct edge
{
int next, to;
/* data */
} e[maxn];
int cnt;
int head[maxn];
void addEdge(int u, int v)
{
e[++cnt] = {head[u], v};
head[u] = cnt;
}
struct node
{
int l, r, flag, w;
int dis() { return r - l + 1; }
int mid() { return (r + l) / 2; }
/* data */
} a[maxn];

int rt;
int cn;
int w[maxn];
int bufW[maxn];
int id[maxn],fa[maxn],top[maxn], son[maxn], dep[maxn], sz[maxn];

void dfs1(int u, int f, int deep)
{
dep[u] = deep;
sz[u] = 1;
fa[u] = f;

int maxSon = -1;
for (int i = head[u]; i; i = e[i].next)
{
int v = e[i].to;
if (v == f)
continue;
dfs1(v, u, deep + 1);
sz[u] += sz[v];
if (sz[v] > maxSon)
{
son[u] = v;
maxSon = sz[v];
}
}
}

void dfs2(int u, int ttop)
{
id[u] = ++cn;
w[cn] = bufW[u];
top[u] = ttop;
if (!son[u])
return;
dfs2(son[u], ttop);
for (int i = head[u]; i; i = e[i].next)
{
int v = e[i].to;
if (v == fa[u] || v == son[u])
continue;
dfs2(v, v);
}
}

void build(int k, int l, int r)
{
a[k] = {l, r, 0, 0};
if (a[k].l == a[k].r)
{
a[k].w = w[r];
return;
}
build(k << 1, l, (r + l) / 2);
build(k << 1 | 1, (r + l) / 2 + 1, r);
a[k].w = a[k << 1].w + a[k << 1 | 1].w;
a[k].w %= mod;
}

void down(int k)
{
a[k << 1].w += a[k << 1].dis() * a[k].flag;
a[k << 1 | 1].w += a[k << 1 | 1].dis() * a[k].flag;
a[k << 1].flag += a[k].flag;
a[k << 1 | 1].flag += a[k].flag;
a[k].flag = 0;
}
void update(int k, int l, int r, int val)
{
if (a[k].l >= l && a[k].r <= r)
{
a[k].w += val * a[k].dis();
a[k].flag += val;
return;
}
if (a[k].flag)
down(k);
if (a[k].mid() >= l)
update(k << 1, l, r, val);
if (a[k].mid() < r)
update(k << 1|1, l, r, val);
a[k].w = a[k << 1].w + a[k << 1 | 1].w;
a[k].w %= mod;
}

int query(int k, int l, int r)
{
if (a[k].l >= l && a[k].r <= r)
return a[k].w;
int res = 0;
if (a[k].flag)
down(k);
if (a[k].mid() >= l)
res += query(k << 1, l, r);
if (a[k].mid() < r)
res += query(k << 1 | 1, l, r);
return res % mod;
}

void updateRange(int p1,int p2,int val){
while (top[p1] != top[p2])
{
if(dep[top[p1]] < dep[top[p2]])
swap(p1,p2);
update(1,id[top[p1]],id[p1],val);
p1 = fa[top[p1]];
}
if(dep[p1] > dep[p2])
swap(p1,p2);
update(1,id[p1],id[p2],val);
}

int queryRange(int p1,int p2){
int ans = 0;
while (top[p1]!=top[p2])
{
if(dep[top[p1]] < dep[top[p2]])
swap(p1,p2);
ans += query(1,id[top[p1]],id[p1]);
ans %= mod;
p1 = fa[top[p1]];
}
if(dep[p1] > dep[p2])
swap(p1,p2);
return (ans + query(1,id[p1],id[p2]))%mod;
}

void updateSon(int p,int val){
update(1,id[p],id[p]+sz[p]-1,val);
}
int querySon(int p){
return query(1,id[p],id[p]+sz[p]-1)%mod;
}

int main()
{
//IN;
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
int n,k,m,rt;
cin >> n >> m >> rt >> mod;
for(int i=1;i<=n;i++)
cin >> bufW[i];
int u,v;

for(int i=1;i<n;i++){
cin >> u >> v;
addEdge(u,v);
addEdge(v,u);
}

dfs1(rt,0,1);
dfs2(rt,rt);
build(1,1,n);

int l, r, w;
while (m--)
{
// debug(n);
cin >> k;
if (k == 1)
{
cin >> l >> r >> w;
updateRange(l, r, w);
}
else if (k == 2)
{
cin >> l >> r;
DEBUG(queryRange(l, r));
}
else if (k == 3)
{
cin >> l >> w;
updateSon(l, w);
}
else
{
cin >> l;
DEBUG(querySon(l));
}
}

return 0;
}

觉得文章不错的话可以请我喝一杯茶哟~
  • 本文作者: bestsort
  • 本文链接: https://bestsort.cn/2019/07/20/720/
  • 版权声明: 本博客所有文章除特别声明外,均采用 BY-SA 许可协议。转载请注明出处!并保留本声明。感谢您的阅读和支持!
-------------本文结束感谢您的阅读-------------