前言

近日,zxy 学习了可持久化线段树并且AC了若干板子题,下面对这种毒瘤数据结构做一个总结

问题引入

给定一个长度为 $n$ 序列 $a_1, a_2, …, a_n$ 和 $m$ 组询问,每次询问给定 3 个数 $l, r, k$,求区间 $[l, r]$ 中,第 $k$ 小的元素是什么。

$O(n ^ 2\log n)$ 的暴力思路显然,这里不做赘述。

从权值线段树到可持久化权值线段树

权值线段树可以说是普通线段树的一个变种,只不过叶子结点维护的是序列中某一权值的个数,而不是对应下标得到权值。

比如说对于下面这个序列:

$$a={1, 1, 4, 5, 1, 4}$$

对应到权值线段树中,每个叶子节点的值为:

  • $v_{[1,1]}=3$,1 出现了 3 次
  • $v_{[2,2]}=0$,2 出现了 0 次
  • $v_{[3,3]}=0$,3 出现了 0 次
  • $v_{[4,4]}=2$,4 出现了 2 次
  • $v_{[5,5]}=1$,5 出现了 1 次

现在回到刚才的问题:如何用权值线段树来求出 整个区间的第 $k$ 小值

用权值线段树维护区间和,即节点$[l, r]$表示满足如下条件的权值(记为$w$)权值出现的次数:$l\leq w\leq r$

那么查询部分有如下代码:

1
2
3
4
5
6
7
inline int query(int u, int l, int r, int k) {
if(l == r) return l; // 二分结束条件
int mid = (l + r) >> 1; // 取中点
int lsum = sum[u << 1]; // 求出左区间出现的权值的个数
if(k <= lsum) return query(u << 1, l, mid, k); // 如果 k 比这个数小,那么在左区间去找
else return query(u << 1 | 1, mid + 1, r, k - lsum); // 否则到右区间去找
}

但是权值可能过大,所以需要离散化。

这种数据结构可以维护绝大部分平衡树可以做到的操作,且代码简单,但需要离散化(是离线数据结构)

现在下面这一道题可以使用这种数据结构求解。

例 1.1

P1801 黑匣子

解法

对于ADD(x)操作,我们将权值线段树中的节点$[x,x]$单点加 1,对于get操作,用上面的代码求区间第 k 小


但是刚才问题中要求的是某一区间的第 k 小值,而非整个区间的第 k 小值。

考虑一种较劣的方法:开 $n$ 棵权值线段树,其中第 $i$ 棵权值线段树维护区间 $[1, i]$。

使用前缀和的思想,一个元素 $x$ 在区间 $[l, r]$ 中出现的次数为 $sum_x(r) - sum_x(l - 1)$

对上面的代码略作修改后,我们得到了一种时间复杂度$O(n \log n)$,空间复杂度 $O(n^2)$ 的算法,现在的问题是:如何节省空间。

发现第 $i$ 棵线段树和第 $i - 1$ 棵线段树只有一条路径上的权值不相同,所以我们可以让这两颗线段树共用其他没有修改的部分,如图所示。

修改了$(1,6)$这一条路径,蓝色的点是新增的节点。

这样一来,每次修改只会增加 $\log n$ 个节点,空间复杂度为 $O(n\log n)$,时间复杂度不变,我们记录每棵线段树的根($T$),每个节点的左儿子($L$)和右儿子($R$)

这种数据结构就叫做可持久化权值线段树(主席树)

例题

警告:下面部分有大量代码,请合理使用目录。

例 2.1 可持久化线段树 1

题意同“问题引入”,提交窗口见P3834 【模板】可持久化线段树 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
#include<bits/stdc++.h>
#define int long long
using namespace std;

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

const int N = 6e6 + 6;
int n, m;
int a[N], b[N];
int L[N], R[N], tot, sum[N], T[N];

inline int build(int l, int r) {
tot++;
int rt = tot;
int mid = (l + r) >> 1;
if(l < r) L[rt] = build(l, mid), R[rt] = build(mid + 1, r);
return rt;
}

inline int update(int pre, int l, int r, int pos) { //修改,在第pre棵树的基础上修改
tot++;
int rt = tot;
L[rt] = L[pre], R[rt] = R[pre], sum[rt] = sum[pre] + 1; // 其他元素与原树相同
if(l < r) {
int mid = (l + r) >> 1;
if(pos <= mid) L[rt] = update(L[pre], l, mid, pos);
else R[rt] = update(R[pre], mid + 1, r, pos);
}
return rt;
}

inline int query(int l, int r, int u, int v, int k) {
if(u == v) return u;
int lsum = sum[L[r]] - sum[L[l]];
int mid = (u + v) >> 1;
if(lsum >= k) return query(L[l], L[r], u, mid, k);
else return query(R[l], R[r], mid + 1, v, k - lsum);
}

signed main() {
n = get(), m = get();
for(register int i = 1; i <= n; i++) a[i] = b[i] = get();
sort(b + 1, b + 1 + n);
int len = unique(b + 1, b + 1 + n) - b - 1;
T[0] = build(1, len);
for(register int i = 1; i <= n; i++) {
int pos = lower_bound(b + 1, b + 1 + len, a[i]) - b;
T[i] = update(T[i - 1], 1, len, pos);
}
for(register int i = 1; i <= m; i++) {
int l = get(), r = get(), k = get();
printf("%d\n", b[query(T[l - 1], T[r], 1, len, k)]);
}
return 0;
}

下面是一些其他的例题,只需要对模板进行一些小改动。

例 2.2 可持久化数组

P3919 【模板】可持久化数组(可持久化线段树/平衡树)

要求写一个数据结构,支持(快速的)历史版本单点修改、单点查询。

与上文的主席树类似,只需要把权值线段树改为普通线段树。

对于操作 1,在第 $v_i$ 棵线段树的基础上做单点修改,对于操作 2,直接继承第 $v_i$ 个树根。

代码

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
#include<bits/stdc++.h>
using namespace std;

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

const int N = 1e6 + 5;
int n, m;
int a[N], tot = 0, sum[N * 30], L[N * 30], R[N * 30], T[N];

inline int build(int l, int r) {
int rt = ++tot;
if(l == r) { sum[rt] = a[l]; return rt; }
int mid = (l + r) >> 1;
L[rt] = build(l, mid), R[rt] = build(mid + 1, r);
return rt;
}

inline int update(int pre, int l, int r, int pos, int v) {
int rt = ++tot;
L[rt] = L[pre], R[rt] = R[pre];
if(l == r && l == pos) {
sum[rt] = v;
return rt;
}
int mid = (l + r) >> 1;
if(pos <= mid) L[rt] = update(L[pre], l, mid, pos, v);
else R[rt] = update(R[pre], mid + 1, r, pos, v);
return rt;
}

inline int query(int u, int l, int r, int pos) {
if(l == r && l == pos) return sum[u];
int mid = (l + r) >> 1;
if(pos <= mid) return query(L[u], l, mid, pos);
else return query(R[u], mid + 1, r, pos);
}

int main() {
n = get(), m = get();
for(register int i = 1; i <= n; i++) a[i] = get();
T[0] = build(1, n);
for(register int i = 1; i <= m; i++) {
int v = get(), opt = get(), loc = get();
if(opt == 1) {
int val = get();
T[i] = update(T[v], 1, n, loc, val);
}
else if(opt == 2) {
printf("%d\n", query(T[v], 1, n, loc));
T[i] = T[v];
}
}
return 0;
}

例 2.3 可持久化并查集

联想到之前写的可持久化数组。

把并查集的 $f$ 数组改用可持久化数组。

但是问题出现了:我们每次只能做一次修改,否则会很麻烦。

这里就需要使用一种全新的思想:启发式合并

维护每一个棵树(并查集本质就是树)中最深的点的深度,然后对于两个要合并的集合,将深度小的合并到深度大的里面。

容易发现:如果两个集合的最深深度($h_x, h_y$)不相等,那么合并后的总深度不变,否则深度为$max{h_x,h_y}+1$。

定义数列$f$表示深度为$x$时集合大小的最小值,显然$f_i = 2f_{i - 1},f_1=1$,求其通项,$f_i=2^{i-1}$,故有:当元素数量为 $x$ 时,最大深度不超过 $\log x$,也就是说我们的复杂度可以保证为 $O(n \log^2 n)$(主席树带一个 log,并查集带一个 log)

代码略。

例 2.4 带修区间第 k 小

P2617 Dynamic Rankings

如果修改了第 x 个数,那么显然第 x 及以后的主席树全部需要进行修改,则时间复杂度高达 $O(n^2\log n)$,只能通过 20% 的数据。

想办法优化这个算法,即尽量减少修改次数。这里使用树套树的思想,用树状数组套主席树,这样一来修改次数从 n 降到了 log n,总复杂度为 $O(n\log^2 n)$

关键部分代码

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
inline int lowbit(int x) { return x & (-x); } //树状数组的 lowbit

inline int query(int l, int r, int k) {
// 查询,bin[1]存储对当前答案有正贡献的树,bin[0]存储对当前答案有负贡献的树
// 求法详见下方 find() 函数
if(l == r) return l;
int lsum = 0;
for(register int i = 1; i <= bin[0][0]; i++) lsum -= sum[L[bin[0][i]]];
for(register int i = 1; i <= bin[1][0]; i++) lsum += sum[L[bin[1][i]]];
int mid = (l + r) >> 1;
if(k <= lsum) {
for(register int i = 1; i <= bin[0][0]; i++) bin[0][i] = L[bin[0][i]];
for(register int i = 1; i <= bin[1][0]; i++) bin[1][i] = L[bin[1][i]];
return query(l, mid, k);
}
else {
for(register int i = 1; i <= bin[0][0]; i++) bin[0][i] = R[bin[0][i]];
for(register int i = 1; i <= bin[1][0]; i++) bin[1][i] = R[bin[1][i]];
return query(mid + 1, r, k - lsum);
}
}

inline int find(int u, int v, int k) {
// 找到查询时有正负贡献的树
memset(bin, 0, sizeof(bin));
int x = u - 1, y = v;
while(x) bin[0][++bin[0][0]] = T[x], x -= lowbit(x);
while(y) bin[1][++bin[1][0]] = T[y], y -= lowbit(y);
return d[query(1, len, k)];
}

inline void add(int u, int v) {
// 同树状数组修改
int pos = lower_bound(d + 1, d + 1 + len, a[u]) - d;
int x = u;
while(x <= n) update(T[x], 1, len, pos, v), x += lowbit(x);
}

写太长了公式都加载不出来了草