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

可持久化数据结构我是一直想写的，今天终于找到机会了。
题目大意：维护一个长度为N的数组，支持单点修改，单点查询历史版本。

思路：
可持久化线段树：每次修改时，新建一个版本的线段树，询问时找到该版本线段树并查询。可每次新建一颗线段树代价太高，于是我们可以考虑每次只新建一部分节点。空间复杂度O(n * 2 + qlogn)，时间复杂度O(nlogn + qlogn)。

具体实现：
0.关于root节点
显然每次操作，root节点都一定会访问到，并且每次都要新建。因此，建立root数组，记录是哪一个版本的root节点。

1.build建树
就像一般的线段树建树就好啦。

	inline void build(int &u, int l, int r){
		u = ++cnt;
		if(l == r){val[u] = read(); return;}
		build(ls[u], l, mid), build(rs[u], mid + 1, r);
	}

2.修改
由于题目只要求单点修改，递归边界就是l == r。每次递归，都要新建一个节点，并把它的左孩子，右孩子等参数与原节点（pre）保持一致。

	inline void New(int &u, int pre, int l, int r, int q, int v){
		u = ++cnt, ls[u] = ls[pre], rs[u] = rs[pre], val[u] = val[pre];
		if(l == r){val[u] = v; return;}
		if(q <= mid) New(ls[u], ls[pre], l, mid, q, v);
		else New(rs[u], rs[pre], mid + 1, r, q, v);
	}

3.查询
题目只要求单点查询，因此只要从该版本的root节点开始递归下去找到那个节点就行了。由于这道题要求查询也算一种操作，所以查询完毕之后直接把root设为该版本的root就行了。

	inline int query(int u, int l, int r, int q){
		if(l == r) return val[u];
		if(q <= mid) return query(ls[u], l, mid, q);
		else return query(rs[u], mid + 1, r, q);
	}

完整代码：

#include<cstdio>
#include<algorithm>
using namespace std;
const int MAXN = 1000005;

int rt[MAXN * 20];

inline int read(){
	int k = 0, f = 1; char ch = getchar();
	while(ch < '0' || ch > '9'){if(ch == '-') f = -1; ch = getchar();}
	while(ch >= '0' && ch <= '9'){k = k*10 + ch - '0'; ch = getchar();}
	return k * f;
}

struct Chairman{
	#define mid ((l + r) >> 1)
	int ls[MAXN * 20], rs[MAXN * 20], val[MAXN * 20], cnt;
	inline void build(int &u, int l, int r){
		u = ++cnt;
		if(l == r){val[u] = read(); return;}
		build(ls[u], l, mid), build(rs[u], mid + 1, r);
	}
	inline void New(int &u, int pre, int l, int r, int q, int v){
		u = ++cnt, ls[u] = ls[pre], rs[u] = rs[pre], val[u] = val[pre];
		if(l == r){val[u] = v; return;}
		if(q <= mid) New(ls[u], ls[pre], l, mid, q, v);
		else New(rs[u], rs[pre], mid + 1, r, q, v);
	}
	inline int query(int u, int l, int r, int q){
		if(l == r) return val[u];
		if(q <= mid) return query(ls[u], l, mid, q);
		else return query(rs[u], mid + 1, r, q);
	}
	#undef mid
}T;

int main(){
	freopen("in.txt", "r", stdin);
	int n = read(), m = read();
	T.build(rt[0], 1, n);
	for(int i = 1; i <= m; i++){
		int pre = read(), opt = read(), x = read(), v;
	switch(opt){
		case 1: v = read(); T.New(rt[i], rt[pre], 1, n, x, v); break;
		case 2: printf("%d\n", T.query(rt[pre], 1, n, x)); rt[i] = rt[pre]; break;
		}
	}
	
	return 0;
}