题解：P3919 【模板】可持久化线段树 1（可持久化数组）

【模板】可持久化线段树 1（可持久化数组）

1. 什么是可持久化线段树

对于每一次修改，这个数据结构都可以清晰地记录下来，并且随时访问某一次修改中的某一个数据。

2. 如何实现可持久化线段树

具体可以看下面的图。

3. 如何编写可持久化线段树

1. 建一棵初始树（操作 $0$）
   其实和线段树的建树过程没有太大的区别。
   CPP

   int build(int p,int pl,int pr){
    	p=++tot;
    	if(pl==pr){
    		tree[p].val=data[pl];
    		return p;
    	}
    	int mid=pl+(pr-pl>>1);
    	tree[p].lson=build(0,pl,mid);
    	tree[p].rson=build(0,mid+1,pr);
    	return p;
    }
   

   注意一下返回的值一定要是整型而不是 void，只有这样才能便于存储左右节点和根节点。
2. 克隆节点（修改以及克隆节点）
   首先，我们修改的时候会有一条链是修改经过的，所以节点的克隆先直接把节点的数据赋值过去即可。
   CPP

   inline int clone(int p){
    	tree[++tot]=tree[p];
    	return tot;
   }
   

   修改操作就是加上克隆操作之后把修改过的节点左儿子或右儿子更新即可。
   CPP

   int modify(int p,int pl,int pr,int L,int R,ll k){
    	p=clone(p);
    	if(L<=pl&&pr<=R){
    		tree[p].val=k;
    		return p;
    	}
    	int mid=pl+(pr-pl>>1);
    	if(L<=mid)tree[p].lson=modify(tree[p].lson,pl,mid,L,R,k);
    	if(mid<R)tree[p].rson=modify(tree[p].rson,mid+1,pr,L,R,k);
    	return p;
   }
   

3. 查询
   正常线段树的查询。
   CPP

   ll query(int p,int pl,int pr,int L,int R){
    	if(L<=pl&&pr<=R){
    		return tree[p].val;
    	}
    	int mid=pl+(pr-pl>>1);
    	ll ret=0;
    	if(L<=mid)ret+=query(tree[p].lson,pl,mid,L,R);
    	if(mid<R)ret+=query(tree[p].rson,mid+1,pr,L,R);
    	return ret;
   }
   

4. 主函数
   根据题目要求，先建出操作 $0$ 的树，然后将每次操作，如果是修改，就把第 $i$ 次操作的根节点更新成新建的树的根即可。
   如果是查询，就把第 $i$ 次操作的根节点更新成第 $v$ 次的操作的根节点。
   CPP

   int main(){
    	n=read(),Q=read();
    	for(int i=1;i<=n;++i){
    		data[i]=read();
    	}
    	root[0]=build(0,1,n);
    	for(int i=1;i<=Q;++i){
    		v=read(),opt=read(),p=read();
    		if(opt==1){
    			c=read();
    			root[i]=modify(root[v],1,n,p,p,c);
    		}else{
    			write(query(root[v],1,n,p,p)),putchar('\n');
    			root[i]=root[v];
    		}
    	}
    	return 0;
    }
   

4. 最后注意的小问题