题目链接
可持久化线段树模板题。
这里总结一下可持久化线段树。
可持久化数据结构就是能恢复历史状态的数据结构，比如可持久化\(Trie\)，并查集，平衡树。
可持久化数组是最基础的，这里通过可持久化线段树来实现。
可持久化线段树
·复杂度：时间\(O(n\log n)\)，空间\(O(m\log n)\)。
·实现：
这里只针对单点修改的可持久化，区间修改是很复杂的。
可以发现，线段树的每次单点修改只会改变树上的\(\log n\)个节点，于是我们对这\(\log n\)个节点创建副本，如图（自绘丑）
红点是我们要修改的点，红边经过的点都是值会发生变化的，我们对其建立副本，如图：
可以看到，每个被修改的点一个副本，和没被修改的点正常连边，这样每次操作只会增加\(\log n\)个节点。
然后我们每次修改把修改后的副本的根记录下来，如图：
然后从这个根遍历树，就是我们要的历史版本了。
代码实现：
#include <cstdio>
#define re register
inline int read(){
s = 0, w = 1;
char ch = getchar();
while(ch < '0' || ch > '9') { if(ch == '-') w = -1; ch = getchar(); }
while(ch >= '0' && ch <= '9') { s = s * 10 + ch - '0'; ch = getchar(); }
return s * w;
}
const int MAXN = 1000010;
const int MAXM = 1000010;
struct SegTree{
int lc, rc, val;
SegTree(){ lc = rc = val = 0; }
}t[MAXM * 20];
int tot, a[MAXN], root[MAXN];
int build(int l, int r){
int id = ++tot;
if(l == r){ t[id].val = a[l]; return id; }
int mid = (l + r) >> 1;
t[id].lc = build(l, mid);
t[id].rc = build(mid + 1, r);
return id;
}
int insert(int now, int l, int r, int x, int p){
int id = ++tot; //创立副本
t[id] = t[now]; //先与原点保持一致
if(l == r){ t[id].val = p; return id; } //修改副本（不改原点）
int mid = (l + r) >> 1;
if(x <= mid) t[id].lc = insert(t[now].lc, l, mid, x, p); //只把改变的儿子变为副本，另一个儿子仍是原来的
else t[id].rc = insert(t[now].rc, mid + 1, r, x, p);
return id; //返回副本编号
}
int ask(int now, int l, int r, int x){ //查询和普通线段树没有区别
if(l == r) return t[now].val;
int mid = (l + r) >> 1;
if(x <= mid) return ask(t[now].lc, l, mid, x);
else return ask(t[now].rc, mid + 1, r, x);
}
int n, m;
int v, opt;
int A, B;
int main(){
n = read(); m = read();
for(int i = 1; i <= n; ++i)
a[i] = read();
root[0] = build(1, n); //初始版本
for(int i = 1; i <= m; ++i){
v = read(); opt = read();
if(opt == 1){
A = read(); B = read();
root[i] = insert(root[v], 1, n, A, B); //在版本v的基础上把位置A上的数变为B
}
else{
A = read();
printf("%d\n", ask(root[v], 1, n, A));
root[i] = root[v];
}
}
return 0;
}