可持久化线段树（单点修改，单点查询）

可持久化线段树（单点修改，单点查询）

给定一个长度为n\mathrm nn的数组arr\mathrm {arr}arr，下标为1∼n\mathrm {1\sim n}1∼n，原始数组认为是0\mathrm 00号版本。一共有m\mathrm mm条操作，每条操作时如下两种类型中的一种：

• v 1 x y\mathrm {v\:1\:x\:y}v1xy：基于v\mathrm vv号版本的数组，把x\mathrm xx位置的值修改为y\mathrm yy，生成新版本的数组。
• v 2 x\mathrm {v\: 2\:x}v2x：基于v\mathrm vv号版本的数组，打印x\mathrm xx位置的值，生成新版本的数组。

每条操作后得到的新版本数组，其版本编号为第i\mathrm ii次操作的操作次序。

题解

对于第i\mathrm ii次操作，其生成的版本就是i\mathrm ii号版本。

因为线段树的递归过程不需要知道父亲是谁，所以理论上我们只要知道每个版本的线段树的根，我们就能够访问这个版本的线段树。

根据可持久化线段树的原理，我们采用结点池的编号法为线段树的结点进行编号，即维护一个全局变量cnt\mathrm{cnt}cnt，表示最新用到的结点数量。

空间大小

每次进行单点修改，都只会涉及树中的一条路径，也就是每次单点修改都会产生log2n\mathrm {log_2n}log2​n个新结点，如果算上原始的数组信息，那么空间大小应该是O(4n+qlog⁡n)\mathrm {O(4n+q\log n)}O(4n+qlogn)，其中q\mathrm qq是询问的次数。

基本信息

constintMAXN=1000001;structNode{intLson,Rson;intval;Node(){Lson=0;Rson=0;val=0;}}tr[25*MAXN];intcnt=0;intversion[25*MAXN];// version[i] 表示第 i 个版本的树根。inta[MAXN];// 原始数组

其中，tr\mathrm {tr}tr是线段树数组，L,R,val\mathrm {L,R,val}L,R,val是每个线段树结点的信息，即左儿子编号、右儿子编号、区间信息。需要注意的是，只有叶子结点的区间信息是有意义的，因为我们要求区间和，所以非叶子结点的val\mathrm {val}val值其实是没意义的。

cnt\mathrm {cnt}cnt是结点池，versioni\mathrm {version_i}versioni​存放的是第i\mathrm ii个版本的树根编号，便于我们查询第i\mathrm ii个版本的线段树，a\mathrm aa数组是原始数组的信息。

接下来我们开始对原始信息建立线段树，于是有build\mathrm {build}build函数。

build\mathrm {build}build函数

intbuild(intL,intR){intnode=++cnt;if(L==R){tr[node].L=0;tr[node].R=0;tr[node].val=a[L];returnnode;}intmid=L+R>>1;intlson=build(L,mid);intrson=build(mid+1,R);tr[node].L=lson;tr[node].R=rson;returnnode;}

值得注意的是，build\mathrm {build}build函数具有返回值，返回的是当前子树的根，比如我们处理左子树时，返回的就是左子树的树根。这是为了便于更新每个结点的左右儿子，且叶子结点的左右儿子编号均为0\mathrm 00，表示不存在。

建立完了初始数组对应的线段树后，设初始数组对应的线段树版本号为0\mathrm 00，则我们令version0=build(1,n)\mathrm {version_0=build(1,n)}version0​=build(1,n)，就是将0\mathrm 00号版本线段树的根结点赋值给version0\mathrm {version_0}version0​。

接下来我们就要解决单点修改的问题。

update\mathrm {update}update函数

intupdate(introot,intL,intR,intpos,intval){intnode=++cnt;tr[node].Lson=tr[root].Lson;tr[node].Rson=tr[root].Rson;tr[node].val=tr[root].val;if(L==R){tr[node].val=val;returnnode;}intmid=L+R>>1;if(pos<=mid)tr[node].Lson=update(tr[root].Lson,L,mid,pos,val);if(pos>mid)tr[node].Rson=update(tr[root].Rson,mid+1,R,pos,val);returnnode;}

update\mathrm {update}update函数的参数分别是root\mathrm {root}root、L\mathrm {L}L、R\mathrm {R}R、pos\mathrm {pos}pos、val\mathrm {val}val，其中L,R\mathrm {L,R}L,R指的是当前结点所表示的区间端点，pos\mathrm {pos}pos表示的是我们要修改的位置，val\mathrm {val}val表示的是要将值修改为val\mathrm {val}val。

其中最重要的是root\mathrm {root}root，它表示上一个版本的表示区间为[L,R]\mathrm {[L,R]}[L,R]的结点编号，为什么要维护root\mathrm {root}root呢？因为我们每次单点修改，只会修改树中的一条路径，而这条路径上的结点的左右结点，除了被修改的，其他的我们希望可以复用上个版本的信息。所以我们需要上一个版本的对应结点编号，先将上个版本的信息复制给当前新节点的左右儿子，然后后面再修改对应的儿子信息即可。

接下来我们处理查询的方法。

query\mathrm {query}query函数

intquery(intnode,intL,intR,intpos){if(L==R){returntr[node].val;}intmid=L+R>>1;if(pos<=mid)returnquery(tr[node].Lson,L,mid,pos);elsereturnquery(tr[node].Rson,mid+1,R,pos);}

query\mathrm {query}query函数实现的是查询某一版本的线段树在pos\mathrm {pos}pos位置上的值，要查询哪个版本的线段树，只需要传入对应版本线段树的树根到node\mathrm {node}node即可。

代码

#include<bits/stdc++.h>usingnamespacestd;//#pragma GCC optimize(2)#defineintlonglong#defineendl'\n'#definePIIpair<int,int>#defineINF1e18constintMAXN=1000001;structNode{intLson,Rson;intval;Node(){Lson=Rson=val=0;}}tr[25*MAXN];intcnt=0;intversion[25*MAXN];// root[i] 表示第 i 个版本的树根。inta[MAXN];// 原始数组intbuild(intL,intR){intnode=++cnt;if(L==R){tr[node].Lson=0;tr[node].Rson=0;tr[node].val=a[L];returnnode;}intmid=L+R>>1;intlson=build(L,mid);intrson=build(mid+1,R);tr[node].Lson=lson;tr[node].Rson=rson;returnnode;}intupdate(introot,intL,intR,intpos,intval){intnode=++cnt;tr[node].Lson=tr[root].Lson;tr[node].Rson=tr[root].Rson;tr[node].val=tr[root].val;if(L==R){tr[node].val=val;returnnode;}intmid=L+R>>1;if(pos<=mid)tr[node].Lson=update(tr[root].Lson,L,mid,pos,val);if(pos>mid)tr[node].Rson=update(tr[root].Rson,mid+1,R,pos,val);returnnode;}intquery(intnode,intL,intR,intpos){if(L==R){returntr[node].val;}intmid=L+R>>1;if(pos<=mid)returnquery(tr[node].Lson,L,mid,pos);elsereturnquery(tr[node].Rson,mid+1,R,pos);}voidslove(){intn,m;cin>>n>>m;for(inti=1;i<=n;i++)cin>>a[i];version[0]=build(1,n);for(inti=1;i<=m;i++){intv,opt;cin>>v>>opt;if(opt==1){intpos,val;cin>>pos>>val;version[i]=update(version[v],1,n,pos,val);}else{intpos;cin>>pos;version[i]=version[v];cout<<query(version[i],1,n,pos)<<endl;}}}signedmain(){ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);slove();}