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

这个题作为主席树的一道模板题，格式有问题，题目就不复制过来了
原题连接
solution：主席树即持久化线段树，如果不懂线段树建议先去看看我的线段树博客

#include <bits/stdc++.h>
using namespace std;

const int maxn = 1000001;
int top = 0, a[maxn], root[maxn];

struct xjp{
	int l, r, val;
}tree[maxn * 20];

//建立新节点
int colne(int node){
	++top;
	tree[top] = tree[node];
	return top;
}

//建树
int maketree(int node, int begin, int end)
{
	node = ++top;
	if (begin == end){
		tree[node].val = a[begin];
		return top;
	}
	int mid = (begin + end) >> 1;
	tree[node].l = maketree(tree[node].l, begin, mid);
	tree[node].r = maketree(tree[node].r, mid + 1, end);
	return node;
}

//更新
int update(int node, int begin, int end, int x, int val)
{
	node = colne(node);
	if (begin == end)tree[node].val = val;
	else{
		int mid = (begin + end) >> 1;
		if (x <= mid)tree[node].l = update(tree[node].l, begin, mid, x, val);
		else tree[node].r = update(tree[node].r, mid + 1, end, x, val);
	}
	return node;
}

//询问
int query(int node, int begin, int end, int x)
{
	if (begin == end)return tree[node].val;
	else {
		int mid = (begin + end) >> 1;
		if (x <= mid)return query(tree[node].l, begin, mid, x);
		else return query(tree[node].r, mid + 1, end, x);
	}
}

int main()
{
	int n, m;
	scanf("%d%d", &n, &m);
	for (int i = 1; i <= n; ++i)scanf("%d", &a[i]);
	root[0] = maketree(0, 1, n);
	for  (int i = 1; i <= m; ++i){
		int rt, mode, x, y;
		scanf("%d%d%d", &rt, &mode, &x);
		if (mode == 1){
			scanf("%d", &y);
			root[i] = update(root[rt], 1, n, x, y);
		}else{
			printf("%d\n", query(root[rt], 1, n, x));
			root[i] = root[rt];
		}
	}
	return 0;
}