主席树------可持久化线段树学习笔记

一.是什么?

可持久化数据结构就是可以访问历史版本的一些数据结构，就像打代码的时候输错了，撤销的操作，很多可持久化数据结构都是增量更新。

二.如何实现

假设我们有\(8\)个数\({6，3，5，4，5，2，1，7}\)，原本的线段树是这样

这是，我们要修改\(12\)号节点我们就这样对每个改动的节点备份一下，像这样

这样就可以找回历史版本了。

三.时间复杂度

和普通线段树一样，查询和修改的操作都是\(O(\log_2n)\)的复杂度，我们只需要注意空间复杂度就好了。

四.实现

P3919 【模板】可持久化线段树 1（可持久化数组）

定义变量

struct TreeNode {
	int lc, rc, val;
} tree[20 * MAXN];
int a[MAXN], b[MAXN], root[MAXN], tot;

建树

int Build(int lt, int rt) {
	int p = ++tot;
	if(lt == rt) {
		tree[p].val = a[lt];
		return p;
	}
	int mid = lt + rt >> 1;
	tree[p].lc = Build(lt, mid);
	tree[p].rc = Build(mid + 1, rt);
	return p;
}

修改

int Modify(int cur, int lt, int rt, int pos, int val) {
	int p = ++tot;
	tree[p] = tree[cur];
	if(lt == rt) {
		tree[p].val = val;
		return p;
	}
	int mid = lt + rt >> 1;	
	if(pos <= mid) tree[p].lc = Modify(tree[cur].lc, lt, mid, pos, val);
	else tree[p].rc = Modify(tree[cur].rc, mid + 1, rt, pos, val);
	return p;
}

查询

int Query(int cur, int lt, int rt, int pos) {
	if(lt == rt) 
		return tree[cur].val;
	int mid = lt + rt >> 1;
	if(pos <= mid) return Query(tree[cur].lc, lt, mid, pos);
	else return Query(tree[cur].rc, mid + 1, rt, pos);
}

完整代码

#include <bits/stdc++.h>
using namespace std;
const int MAXN = 1000005;
const int MAXM = 1000005;
struct TreeNode {
	int lc, rc, val;
} tree[20 * MAXN];
int a[MAXN], b[MAXN], root[MAXN], tot;
int n, m;

int Build(int lt, int rt) {
	int p = ++tot;
	if(lt == rt) {
		tree[p].val = a[lt];
		return p;
	}
	int mid = lt + rt >> 1;
	tree[p].lc = Build(lt, mid);
	tree[p].rc = Build(mid + 1, rt);
	return p;
}
int Modify(int cur, int lt, int rt, int pos, int val) {
	int p = ++tot;
	tree[p] = tree[cur];
	if(lt == rt) {
		tree[p].val = val;
		return p;
	}
	int mid = lt + rt >> 1;	
	if(pos <= mid) tree[p].lc = Modify(tree[cur].lc, lt, mid, pos, val);
	else tree[p].rc = Modify(tree[cur].rc, mid + 1, rt, pos, val);
	return p;
}
int Query(int cur, int lt, int rt, int pos) {
	if(lt == rt) 
		return tree[cur].val;
	int mid = lt + rt >> 1;
	if(pos <= mid) return Query(tree[cur].lc, lt, mid, pos);
	else return Query(tree[cur].rc, mid + 1, rt, pos);
}


int main() {
	cin >> n >> m;
	for(int i = 1; i <= n; i ++) {
		scanf("%d", &a[i]);
	}
	root[0] = Build(1, n);
	for(int i = 1; i <= m; i ++) {
		int ver, pos, val, op;
		scanf("%d%d%d", &ver, &op, &pos);
		if(op == 1) {
			scanf("%d", &val);
			root[i] = Modify(root[ver], 1, n, pos, val);
		}
		if(op == 2) {
			printf("%d\n", Query(root[ver], 1, n, pos));
			root[i] = root[ver];
		}
	}
	return 0;
}