可持久化的数据结构就是可以访问历史版本的数据结构,那么可持久化数组就是可以访问历史版本的数组

朴素做法

每操作一次数组,就复制一个同样的数组存起来,访问历史版本数据的时间复杂度为O(1),但是复制操作的时间复杂度为O(n),并且每次都复制相同大小的数组,非常容易MLE+TLE

空间换时间

有没有什么数据结构能够在复制的时候很快且查询起来不会很久呢?答案是有的,我们可以用可持久化线段树来维护数组信息,查询和复制的时间复杂度都是O(logn)的,且能够有效减少复制时的空间消耗,查询时间也是可接受的。

不会可持久化线段树的建议先去学习一下,可以看看这一篇Blog。

可持久化数组

非叶子结点维护什么信息?

通常线段树的非叶子结点都会维护一些信息,比如区间和、区间最值等,但是对于可持久化数组来说,线段树的非叶子结点并不需要维护任何信息。

是否需要建树?

在学习主席树的时候,我们是不需要建树操作的,或者说编译器帮我们建好了。那是因为主席树维护的是点的权值,初始化时权值都为0,而全局变量初始化为0,所以不需要额外的建树操作。

但是对于可持久化数组来说,我们维护的是普通的线段树而不是权值线段树,所以是需要建树操作的。

所需要的全局变量

首先我们需要一个struct来存储树的结点,同时把线段树的空间开好,这里开了40倍。

struct node {
	int l, r, val;
}tree[maxn * 40];

同时需要一个root[]数组维护每一个版本根节点的序号,一个a[]数组存储数组的数据。

用一个int cnt来开辟新的结点

建树

建树操作非常的简单,和普通的线段树没什么差别,但是需要注意的是当前结点序号now需要传引用

// now: 当前结点序号
void build(int l, int r, int &now) {
	now = ++cnt;
	if (l == r) {
		tree[now].val = a[l];
		return;
	}
	int mid = (l + r) >> 1;
	build(l, mid, tree[now].l);
	build(mid+1, r, tree[now].r);
}

修改

修改前先复制一份pre版本,然后再修改即可

void modify(int l, int r, int pre, int &now, int pos, int val) {
	now = ++cnt;
	tree[now] = tree[pre];
	if (l == r) {
		tree[now].val = val;
		return ;
	}
	int mid = (l + r) >> 1;
	if (pos <= mid) modify(l, mid, tree[pre].l, tree[now].l, pos, val);
	else modify(mid+1, r, tree[pre].r, tree[now].r, pos, val);
}

查询

查询就更加的简单了

int query(int l, int r, int now, int pos) {
	if (l == r) return tree[now].val;
	int mid = (l + r) >> 1;
	if (pos <= mid) return query(l, mid, tree[now].l, pos);
	else return query(mid+1, r, tree[now].r, pos);
}

洛谷P3919

一道可持久化数组的模板题洛谷P3919

p3919

// 样例输入
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

// 样例输出
59
87
41
87
88
46
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
#define inf 0x3f3f3f3f
#define INF 0x3f3f3f3f3f3f3f3f
#define IO ios::sync_with_stdio(0)
#define DEBUG(x) cout<<"--->"<<(x)<<endl;
typedef pair<int, int> P;
const ll mod = 1e9+7;
const double eps = 1e-9;
const double PI = acos(-1);
const int maxn = 1e6+5;

struct node {
	int l, r, val;
}tree[maxn * 40];

int root[maxn], a[maxn];
int cnt;

void build(int l, int r, int &now) {
	now = ++cnt;
	if (l == r) {
		tree[now].val = a[l];
		return;
	}
	int mid = (l + r) >> 1;
	build(l, mid, tree[now].l);
	build(mid+1, r, tree[now].r);
}

void modify(int l, int r, int pre, int &now, int pos, int val) {
	now = ++cnt;
	tree[now] = tree[pre];
	if (l == r) {
		tree[now].val = val;
		return ;
	}
	int mid = (l + r) >> 1;
	if (pos <= mid) modify(l, mid, tree[pre].l, tree[now].l, pos, val);
	else modify(mid+1, r, tree[pre].r, tree[now].r, pos, val);
}

int query(int l, int r, int now, int pos) {
	if (l == r) return tree[now].val;
	int mid = (l + r) >> 1;
	if (pos <= mid) return query(l, mid, tree[now].l, pos);
	else return query(mid+1, r, tree[now].r, pos);
}

int main() {
	int n, m;
	scanf("%d%d", &n, &m);
	for (int i=1; i<=n; i++) scanf("%d", &a[i]);
	build(1, n, root[0]);
	for (int i=1; i<=m; i++) {
		int ver, opt;
		scanf("%d%d", &ver, &opt);
		if (opt == 1) {
			int pos, val;
			scanf("%d%d", &pos, &val);
			modify(1, n, root[ver], root[i], pos, val);
		} else {
			int pos;
			scanf("%d", &pos);
			printf("%d\n", query(1, n, root[ver], pos));
			root[i] = root[ver];
		}
	}
	return 0;
}

推荐视频

AgOH–可持久化数组