UPDATE : 最后一个点时间空间已经放大
标题即题意
有了可持久化数组，便可以实现很多衍生的可持久化功能（例如：可持久化并查集）
如题，你需要维护这样的一个长度为 NN 的数组，支持如下几种操作
在某个历史版本上修改某一个位置上的值
访问某个历史版本上的某一位置的值
此外，每进行一次操作（对于操作2，即为生成一个完全一样的版本，不作任何改动），就会生成一个新的版本。版本编号即为当前操作的编号（从1开始编号，版本0表示初始状态数组）
输入格式：
输入的第一行包含两个正整数 N, M， 分别表示数组的长度和操作的个数。
第二行包含N个整数，依次为初始状态下数组各位的值（依次为 ai?，1≤i≤N）。
接下来M行每行包含3或4个整数，代表两种操作之一（i为基于的历史版本号）：
对于操作1，格式为vi? 1 loci? valuei?，即为在版本vi?的基础上，将 aloci?? 修改为valuei?
对于操作2，格式为vi? 2 loci?，即访问版本vi?中的 aloci??的值，生成一样版本的对象应为vi
输出格式：
输出包含若干行，依次为每个操作2的结果。
数据规模：
对于30%的数据：1≤N,M≤10^3
对于50%的数据：1≤N,M≤10^4
对于70%的数据：1≤N,M≤10^5
对于100%的数据：1≤N,M≤10^6,1≤loci?≤N,0≤vi?<i,−10^9≤ai?,valuei?≤10^9
经测试，正常常数的可持久化数组可以通过，请各位放心
数据略微凶残，请注意常数不要过大
另，此题I/O量较大，如果实在TLE请注意I/O优化
询问生成的版本是指你访问的那个版本的复制
样例说明：
一共11个版本，编号从0-10，依次为：
* 0 : 59 46 14 87 41
* 1 : 59 46 14 87 41
* 2 : 14 46 14 87 41
* 3 : 57 46 14 87 41
* 4 : 88 46 14 87 41
* 5 : 88 46 14 87 41
* 6 : 59 46 14 87 41
* 7 : 59 46 14 87 41
* 8 : 88 46 14 87 41
* 9 : 14 46 14 87 41
* 10 : 59 46 14 87 91
1 #include<iostream> 2 #include<cstdio> 3 #include<algorithm> 4 #include<cstring> 5 #define mid ((l+r)>>1) 6 using namespace std; 7 long long read() 8 { 9 long long x=0,f=1; 10 char ch=getchar(); 11 while(ch<‘0‘||ch>‘9‘) 12 { 13 if(ch==‘-‘) 14 f=-1; 15 ch=getchar(); 16 } 17 while(ch>=‘0‘&&ch<=‘9‘) 18 { 19 x=x*10+ch-‘0‘; 20 ch=getchar(); 21 } 22 return x*f; 23 } 24 struct node 25 { 26 int rt[1000001],T[20000001],L[20000001],R[20000001]; 27 int cnt; 28 int build(int l,int r) 29 { 30 int root=++cnt; 31 if(l==r) 32 { 33 T[root]=read(); 34 return root; 35 } 36 L[root]=build(l,mid); 37 R[root]=build(mid+1,r); 38 return root; 39 } 40 int update(int pre,int l,int r,int &x,int &c) 41 { 42 int root=++cnt; 43 if(l==r) 44 { 45 T[root]=c; 46 return root; 47 } 48 L[root]=L[pre]; 49 R[root]=R[pre]; 50 51 if(x<=mid) 52 L[root]=update(L[pre],l,mid,x,c); 53 else 54 R[root]=update(R[pre],mid+1,r,x,c); 55 return root; 56 } 57 void query(int pre,int l,int r,int& x) 58 { 59 if(l==r) 60 { 61 printf("%d\n",T[pre]); 62 return; 63 } 64 if(x<=mid) 65 query(L[pre],l,mid,x); 66 else 67 query(R[pre],mid+1,r,x); 68 } 69 } iu; 70 int n,m,v,cd,x,y; 71 int main() 72 { 73 iu.cnt=0; 74 n=read(),m=read(); 75 iu.build(1,n); 76 iu.rt[0]=1; 77 for(int i=1; i<=m; i++) 78 { 79 v=read(),cd=read(),x=read(); 80 if(cd==1) 81 { 82 y=read(); 83 iu.rt[i]=iu.update(iu.rt[v],1,n,x,y); 84 } 85 if(cd==2) 86 { 87 iu.rt[i]=iu.rt[v]; 88 iu.query(iu.rt[v],1,n,x); 89 } 90 } 91 return 0; 92 }
洛谷P3919 【模板】可持久化数组（可持久化线段树/平衡树）
原文：https://www.cnblogs.com/liweilin/p/10188732.html
