本文共 1769 字，大约阅读时间需要 5 分钟。

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

题目链接： /

题目大意

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

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

思路

这道题其实就是模板题。

它就是在线段树的基础上弄的。

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

然后你会发下每次操作根都一定会弄一个新的点，那我们查询的时候就可以从这个地方开始找。

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

代码

#include
   
    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;}