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

题目链接：luogu P3919

题目大意

有个数组，你要支持几种操作。

在某个历史版本的基础上修改某个位置的值。
在某个历史版本上询问某个位置的值。

思路

这道题其实就是模板题。

它就是在线段树的基础上弄的。
你先想想这道题的暴力做法，就是开很多个数组，记录每个历史状态。

那它就是用线段树记录状态，然后每次更新值会要走一条链，就把这条链上的点都更新，换成一个新的点。
这样就不用每次就重新换一个树，从而减小空间。

然后你会发下每次操作根都一定会弄一个新的点，那我们查询的时候就可以从这个地方开始找。
也就是把每个根都记录下来，这样你就可以选择看哪个历史版本了。

当然这里无论是什么操作都会返回值，最外层返回的是根节点的编号，里面的就是左儿子或者有儿子的编号。那这个线段树看儿子就不是乘二和乘二加一了。
你就要弄一个结构体，记录两个儿子的位置编号。

代码

#include<cstdio>

using namespace std;

struct node {
	int l, r, x;
}tree[20000001];
int n, m, a[1000001], num;
int root[1000001], v, op, loc, value;

int clone(int now) {//增加新的节点
	num++;
	tree[num] = tree[now];
	return num;
}

int build(int now, int l, int r) {//建一开始的数
	now = ++num;
	
	if (l == r) {
		tree[now].x = a[l];
		return now;
	}
	
	int mid = (l + r) >> 1;
	tree[now].l = build(tree[now].l, l, mid);
	tree[now].r = build(tree[now].r, mid + 1, r);
	
	return now;
}

int change(int now, int l, int r, int loc, int value) {//改变一个值
	now = clone(now);//要改的点询问的路径都要变成新的
	
	if (l == r) {
		tree[now].x = value;
		return now;
	}
	
	int mid = (l + r) >> 1;
	if (loc <= mid) tree[now].l = change(tree[now].l, l, mid, loc, value);
		else tree[now].r = change(tree[now].r, mid + 1, r, loc, value);
	
	return now;
}

int ask(int now, int l, int r, int loc) {//询问一个值
	if (l == r) {
		return tree[now].x;
	}
	
	int mid = (l + r) >> 1;
	if (loc <= mid) return ask(tree[now].l, l, mid, loc);
		else return ask(tree[now].r, mid + 1, r, loc);
}

int main() {
	scanf("%d %d", &n, &m);
	for (int i = 1; i <= n; i++) scanf("%d", &a[i]);
	
	root[0] = build(0, 1, n);
	
	for (int i = 1; i <= m; i++) {
		scanf("%d %d %d", &v, &op, &loc);
		
		if (op == 1) {
			scanf("%d", &value);
			root[i] = change(root[v], 1, n, loc, value);
		}
		else {
			printf("%d\n", ask(root[v], 1, n, loc));
			root[i] = root[v];
		}
	}
	
	return 0;
}