【主席树】luogu_3919 可持久化数组（可持久化线段树/平衡树）

本文主要是介绍【主席树】luogu_3919 可持久化数组（可持久化线段树/平衡树），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题意

如题，你需要维护这样的一个长度为 $N$ 的数组，支持如下几种操作：

1、在某个历史版本上修改某一个位置上的值

2、访问某个历史版本上的某一位置的值

思路

主席树模板

代码

#include<cstdio>
#include<algorithm>struct SegmentTree {int lc, rc;int dat;
} tree[20000001];
int a[1000001], root[1000001];
int tot, n, m;int build(int l, int r) {int p = ++tot;if (l == r) {tree[p].dat = a[l];return p;}int mid = (l + r) >> 1;tree[p].lc = build(l, mid);tree[p].rc = build(mid + 1, r);return p;
}int modify(int now, int l, int r, int x, int val) {int p = ++tot;tree[p] = tree[now];if (l == r) {tree[p].dat = val;return p;}int mid = (l + r) >> 1;if (x <= mid)tree[p].lc = modify(tree[now].lc, l, mid, x, val);elsetree[p].rc = modify(tree[now].rc, mid + 1, r, x, val);return p;
}int ask(int now, int l, int r, int x) {if (l == r) return tree[now].dat;int mid = (l + r) >> 1;if (x <= mid) return ask(tree[now].lc, l, mid, x);else return ask(tree[now].rc, mid + 1, r, x);
}int main() {scanf("%d %d", &n, &m);for (int i = 1; i <= n; i++)scanf("%d", &a[i]);root[0] = build(1, n);int ver, op, w, v;for (int i = 1; i <= m; i++) {scanf("%d %d", &ver, &op);if (op == 1) {scanf("%d %d", &w, &v);root[i] = modify(root[ver], 1, n, w, v);} else {scanf("%d", &w);printf("%d\n", ask(root[ver], 1, n, w));root[i] = root[ver];}}
}