例题：P3919 【模板】可持久化线段树 1（可持久化数组）
写在前面
我是蒟蒻，不会区间修改，只知道要。
思想
可持久化数组要求修改之前的版本，所以我们必须保存之前的版本，但是对于每次都再建一颗线段树，空间是极大的，所以我们考虑优化。
我们修改图中的黄色节点，线段树从前一棵变为了后一棵。
注意到，图中的红色框中的节点是相同的，所以我们考虑重复利用节点。
下图展示了可持久化数组的结构。
图中的红色连边是重复利用节点的关键，我们注意到三个关键点：
\(1.\)图中不只有一个根节点。
\(2.\)每一个根节点都构成一棵线段树，都对应一个版本。
\(3.\)每一次修改只会增加\(\log_{2}n\)个节点。
所以现在思路就很明显了。
下面给出代码，对照代码理解。
\(Code:\)
#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int N=1e6+5,INF=2e9+5;
int tot=0,rt[N];//tot为点数，rt[]为根节点编号
struct node{
int l,r,val;//节点的储存，分别为：左子节点，右子节点，点权值
}tree[N<<5];//要注意细节，空间要开到20倍，所以至少位移5位
inline int read(){//读入优化
int x=0;bool s=0;char c=getchar();
while(c<'0'||c>'9'){if(c=='-')s=1;c=getchar();}
while('0'<=c&&c<='9'){x=(x<<3)+(x<<1)+(c^48);c=getchar();}
return s?-x:x;
}
int copy(int i){//复制节点，将下一个节点复制为tree[i]
tree[++tot]=tree[i];
return tot;
}
int build(int left,int right){//建树
int i=++tot;//
if(left==right){//到叶节点
tree[i].val=read();//读入边权
tree[i].l=tree[i].r=INF;//没有左右孩子
return i;
}
int mid=left+right>>1;//递归建左右子树
tree[i].l=build(left,mid);
tree[i].r=build(mid+1,right);
return i;
}
int update(int i,int left,int right,int x,int y){//修改操作
int point=copy(i);//复制i节点
if(left==right){//到根节点
tree[point].val=y;//修改权值
tree[point].l=tree[point].r=INF;
}
else{//没找到
int mid=left+right>>1;//递归去找
if(x<=mid)tree[point].l=update(tree[point].l,left,mid,x,y);
else tree[point].r=update(tree[point].r,mid+1,right,x,y);
}
return point;
}
int query(int i,int left,int right,int x){//查询
if(left==right)return tree[i].val;
else{
int mid=left+right>>1;
if(x<=mid)return query(tree[i].l,left,mid,x);
else return query(tree[i].r,mid+1,right,x);
}
}
int main(){
int n=read(),m=read();
rt[0]=build(1,n);
for(int i=1;i<=m;i++){
int v=read(),op=read(),loc=read();
if(op==1){
int value=read();
rt[i]=update(rt[v],1,n,loc,value);
}
else{
printf("%d\n",query(rt[v],1,n,loc));
rt[i]=rt[v];
}
}
return 0;
}