可持久化数组

例题：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("%dn",query(rt[v],1,n,loc));
			rt[i]=rt[v];
		}
	}
	return 0;
}