洛谷 P3919 【模板】可持久化数组（可持久化线段树/平衡树）

缘起

开始研究可持久化数据结构以及一些有趣的各种树结构啦~ 洛谷 P3919 【模板】可持久化数组（可持久化线段树/平衡树

分析

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
题目描述
你需要维护这样的一个长度为N的数组，支持如下几种操作

1. 在某个历史版本上修改某一个位置上的值
2. 访问某个历史版本上的某一位置的值
此外，每进行一次操作（对于操作2，即为生成一个完全一样的版本，不作任何改动），就会生成一个新的版本。版本
编号即为当前操作的编号（从1开始编号，版本0表示初始状态数组）

输入输出格式
输入格式：
输入的第一行包含两个正整数N,M分别表示数组的长度和操作的个数。
第二行包含 N N个整数，依次为初始状态下数组各位的值（依次为ai，1≤i≤N）。
接下来M行每行包含3或4个整数，代表两种操作之一（i为基于的历史版本号）：
对于操作1，格式为vi 1 loc_{i} value_{i}，即为在版本vi的基础上，将a_{loc_{i}}修改为value_{i}
对于操作2，格式为vi 2 loc_{i}，即访问版本vi中的a_{loc_{i}}的值, 而且生成一个和vi一模一样的版本出来

输出格式：
输出包含若干行，依次为每个操作2的结果。

输入样例#1：
5 10
59 46 14 87 41
0 2 1
0 1 1 14
0 1 1 57
0 1 1 88
4 2 4
0 2 5
0 2 4
4 2 1
2 2 2
1 1 5 91

输出样例#1：
59
87
41
87
88
46

对于100%的数据：1≤N,M≤10^6,1≤loci≤N,0≤vi<i,−10^9≤ai,value_i≤10^9

样例说明：
一共11个版本，编号从0-10，依次为：
0 : 59 46 14 87 41
1 : 59 46 14 87 41
2 : 14 46 14 87 41
3 : 57 46 14 87 41
4 : 88 46 14 87 41
5 : 88 46 14 87 41
6 : 59 46 14 87 41
7 : 59 46 14 87 41
8 : 88 46 14 87 41
9 : 14 46 14 87 41
10 : 59 46 14 87 91

时间限制 3s, 内存限制 500MB

如果此题仅仅是更新, 然后获取当前某索引下的元素的话, 则根本连线段树都不需要用——直接用数组就够了. 但是现在要求能够访问到历史版本（这就是可持久化的意思）.但是你不能对每个版本都建立一个数组——慢不说，而且一定会MLE. 所以本题就是要你写一个可持久化数组的数据结构, 能够方便的维护并访问历史版本——哎呀, 我觉得这种可持久化数据结构在mysql的MVCC机制中一定非常有用~

那么该怎么做到呢? 这里我参阅了【1】, 一篇神犇的文章 or2

首先, 我们来看看暴力怎么写， 然后看看怎么从最原始的程序一步一步演化到可持久化线段树.

暴力的思想很简单, 就是每次都暴力for生成一个新的版本。

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
//#include "stdafx.h"
#include <stdio.h>
#include <vector>
using namespace std;
//#define LOCAL

const int maxn = 1e6+5;
int n,m;
vector<int> g[maxn];

int main() {
#ifdef LOCAL
	freopen("d:\\data.in", "r", stdin);
//	freopen("d:\\my.out", "w", stdout);
#endif
	scanf("%d%d", &n, &m);
	for (int i = 1,x;i<=n; i++)
	{
		scanf("%d", &x);
		g[i].push_back(x);
	}
	while(m--)
	{
		int a,b,c,d;
		scanf("%d%d%d", &a, &b, &c);
		if (b==1)
		{
			scanf("%d", &d);
		}
		if (b==2) // 访问历史版本的元素
		{
			printf("%d\n", g[c][a]);
			for (int i = 1;i<=n; i++)
			{
				g[i].push_back(g[i].back());
			} // 因为要生成一样的版本
		}
		else // 更新一个元素
		{
			for (int i = 1;i<=n; i++)
			{
				if (i!=c) // 不是c的需要一样
				{
					g[i].push_back(g[i].back());
				}
				else
				{
					g[c].push_back(d);
				}
			}
			
		}
	}
	return 0;
}

说白了, 上面的代码就是像下图维护版本的

上面的代码很快被MLE掉了.而且瞎眼可见的高复杂度——我每次就更新一个元素, 竟然要再将所有其他根本没有更新过的元素也重新塞一遍. 为什么要这样做呢? 原因很简单——因为数组元素要能被索引到. 如果你不重新塞一遍的话, 我是没办法索引到的. 所以就要引入树的概念——我们对每个版本都引入一个树的根,然后通过树根来索引到这个版本的所有元素. 那么这个树根是什么树的树根? 既然是数组, 是一段索引区间，那自然是线段树最好不过了. 所以我们对每个版本都维护一棵线段树.则N个版本需要维护N棵线段树, 等一下~ 这样不还是会MLE吗? 究其根本是因为没有解决——我仅仅更新一个元素, 为什么要将其他没更新的元素重新塞一遍呢? 而理想的解决方案是——空间复用, 即对于没有更新的元素, 我直接复用历史版本的内存空间——而计算机中复用空间的方式就是指针, 让指针指向历史版本就好了. 注意, 不要小瞧了本题的空间复用, 空间复用了, 则就不需要像暴力版本写法那样使用for维护新版本了, 时间复杂度也就跟着降下来了.

首先, 对于本题的初始版本, 它对应的线段树如下图所示

而版本0只是被查询了一下，然后跟初始版本一模一样（即版本1和版本0一模一样）。这就没必要复制了嘛！我们设版本i有一个根节点root_i（线段树的根节点表示整段区间），根节点有左右儿子，那么我们直接让root1的左右儿子指向root0的左右儿子就好了，根本不用复制整个线段树嘛！

那再来看看修改操作。比如从版本0修改一个元素到版本2。版本2会长这样——

有没有发现版本2和版本0真的很像？其实从前到后只改变了一个节点（就是最左下角的那个14）！那么其他相同的地方，我们可不可以共用一段内存呢？

有没有发现1和2真的很像？其实从前到后只改变了一个节点！那么其他相同的地方，我们可不可以共用一段内存呢？ 完全可以呀~ 像下图展示的那样. ps: 下图其实更确切右边的应该是版本0而不是版本1(因为样例数据版本2是在版本0的基础上构建的), 但就本题而言. 版本1和版本0是一样的. 所以就拿版本1来举例了.

没错，每次创建一个新的版本时，只要新建logn个节点,也就是只保存从新版本的根节点到更新的那一个叶子节点的路径就可以了，不在此路径上的左/右儿子只要接原版本对应区间的对应儿子就可以啦。我们可以保证，从对应版本的根节点一定能访问到对应叶子节点的值. 不难看出可持久化线段树的时空复杂度是 O(nlogn)的, log是以2为底的对数, 所以本题的空间最大要直奔2000w去了. QAQ

这就是持久化线段树的核心思想!

注意, 因为本题涉及多棵线段树, 所以最好不要采用【3】中建树的 cur <<1 和 cur<<1|1 作为子节点的方式. 而是采用【2】中提及的空间复杂度优化的写法. 不过这样的话, 就要维护线段树节点的左右孩子索引

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
//#include "stdafx.h"
#include <stdio.h>
//#define LOCAL

const int maxn = 1000005;
int n,m, a[maxn], cnt, version; // cnt是线段树节点个数, version是版本个数
struct PersistentSegmentTreeNode
{
	int begin,end,l,r,val; // 当前持久化线段树节点表示[begin,end], mid是(begin+end)>>1, val仅仅是叶子节点的时候才有意义
}persistentSegmentTree[maxn<<4]; // 注意, 因为可持久化线段树的空间复杂度是O(nlogn),logn是以2位底的对数, 所以对于100w的规模, 就直奔2000w去了.

int ver[maxn]; // ver[i]表示第i个版本对应的线段树根节点索引, 因为最后要访问某个节点的某个版本, 所以要找到该版本对应的线段树的根节点才能访问下去

int build(int begin, int end) // 构建线段树,返回新建的线段树的根节点
{
	int root = ++cnt; // 要返回的此线段树根节点索引
	persistentSegmentTree[root].begin = begin;
	persistentSegmentTree[root].end = end;
	if (begin==end)
	{
		persistentSegmentTree[root].val = a[begin];
		return root;
	}
	int mid = persistentSegmentTree[root].begin+persistentSegmentTree[root].end>>1;
	persistentSegmentTree[root].l = build(begin, mid);
	persistentSegmentTree[root].r = build(mid+1, end);
	return root;
}

int newnode(int i) // 以 persistentSegmentTree[i]为模板构造新的节点
{
	int root = ++cnt;
	persistentSegmentTree[root].begin = persistentSegmentTree[i].begin;
	persistentSegmentTree[root].end = persistentSegmentTree[i].end;
	persistentSegmentTree[root].l = persistentSegmentTree[i].l;
	persistentSegmentTree[root].r = persistentSegmentTree[i].r;
	return root;
}

int updata(int loc, int val, int cur) // 修改 a[loc]为val, 返回新的版本对应的线段树的根节点.
{
	if (persistentSegmentTree[cur].begin==persistentSegmentTree[cur].end)
	{
		int root = newnode(cur);
		persistentSegmentTree[root].val = val;
		return root;
	}
	int mid = persistentSegmentTree[cur].begin+persistentSegmentTree[cur].end>>1, other, me; // other是另一边（只需要指针指向, 而不需要完整复制）, me是复制出来的新节点
	bool flag; // true表示other是其父节点的左孩子, false表示其父节点的右孩子
	if (loc<=mid)
	{
		other = persistentSegmentTree[cur].r; // 不需要新建, 直接指针指向的节点
		flag = false;
		me = updata(loc, val, persistentSegmentTree[cur].l); // 要复制出来的节点
	}
	else
	{
		other = persistentSegmentTree[cur].l;
		flag = true;
		me = updata(loc, val, persistentSegmentTree[cur].r);
	}
	int root = newnode(cur); // 新建当前节点
	persistentSegmentTree[root].l = flag?other:me;
	persistentSegmentTree[root].r = flag?me:other;
	return root;
}

int query(int loc, int cur)
{
	if (persistentSegmentTree[cur].begin==persistentSegmentTree[cur].end) // 那一定和loc相等
	{
		return persistentSegmentTree[cur].val;
	}
	int mid = persistentSegmentTree[cur].begin+persistentSegmentTree[cur].end>>1;
	return loc<=mid?query(loc, persistentSegmentTree[cur].l):query(loc, persistentSegmentTree[cur].r);
}

int main() {
#ifdef LOCAL
	freopen("d:\\data.in", "r", stdin);
//	freopen("d:\\my.out", "w", stdout);
#endif
	scanf("%d%d", &n, &m);
	for (int i = 1;i<=n; i++)
	{
		scanf("%d", a+i);
	}
	ver[version] = build(1,n); // 建树作为0号最初版本
	while(m--)
	{
		++version; // 本题每次操作版本都会+1
		int v,typa,loc, val;
		scanf("%d%d%d", &v, &typa, &loc);
		if (typa&1) // 更新
		{
			scanf("%d", &val);
			ver[version] = updata(loc,val, ver[v]); // 新的版本对应的线段树的根节点索引由updata方法返回
		}
		else // 访问历史版本v的loc处的数据
		{
			printf("%d\n", query(loc, ver[v])); // 从ver[v]（版本v的线段树对应的根节点打下去查找）
			ver[version] = newnode(ver[v]);// 复制一个版本出来,简单的指向就完成了新版本的线段树的构造而不需要完整复制(即所谓的浅复制)
		}
	}
	return 0;
}

ac情况

1
2
3
4
5
6
所属题目
P3919 【模板】可持久化数组（可持久化线段树/平衡树）
评测状态
Accepted
评测分数
100

喜提可持久化线段树模板一枚!

参考

【1】https://www.cnblogs.com/flashhu/p/8297581.html

【2】https://yfsyfs.github.io/2019/09/20/%E6%B4%9B%E8%B0%B7-P4357-CQOI2016-K%E8%BF%9C%E7%82%B9%E5%AF%B9-kd%E6%A0%91/

【3】https://yfsyfs.github.io/2019/07/13/%E7%BA%BF%E6%AE%B5%E6%A0%91/