可持久化线段树主要用于对于历史版本的查询修改。 举个例子,目前修改了10次,现在要返回第7次修改后的版本进行查询修改,那么这样就要用到可持久化线段树。
当你要进行对于历史版本的查询修改,自然要记录历史版本,但如果对于每个历史版本建立都一棵新的线段树,显然会爆空间。那如何使用可持久化线段树呢。
先看一幅图: 灰色的节点是不存在的,只是意义上的。 红色线是连到前一棵树的 现在修改i这个位置,i’是修改后的i,i’和它的所有祖先都是新建的节点。 容易看出,原理就是: 对于每个被修改的位置,对于它与它的所有祖先新建一个点。而没有被修改的点与修改前的线段树上的点共用。
这里借用了zz的code
#include<cstdio> #include<cstring> #include<algorithm> #include<cstdlib> #include<cmath> #define fo(i,a,b) for(int i=a;i<=b;i++) #define N 10100000 using namespace std; struct note{ int l,r,data,lazy; }; note tree[N]; int n,a[N],g[N],tot=1,ans,tt=1; void build(int v,int i,int j) { if (i==j) {tree[v].data=a[i];return;} int mid=(i+j)/2; tree[v].l=++tot;build(tot,i,mid); tree[v].r=++tot;build(tot,mid+1,j); tree[v].data=max(tree[tree[v].l].data,tree[tree[v].r].data); } void down(int v,int i,int j)//下传标记 { if (i==j) {tree[v].lazy=0;return;} int mid=(i+j)/2; //对于每个被修改的位置,新建一个点。并将原来的值就该 tree[++tot]=tree[tree[v].l]; tree[tot].lazy+=tree[v].lazy; tree[v].l=tot; tree[tot].data+=tree[v].lazy; tree[v].r=tot; tree[v].lazy=0; } void insert(int v,int i,int j,int x,int y,int z) { if (i==x && j==y) {tree[v].data+=z;tree[v].lazy+=z;return;} int bz=0; if (tree[v].lazy) down(v,i,j),bz=1; int mid=(i+j)/2; if (y<=mid) { if (!bz) tree[++tot]=tree[tree[v].l],tree[v].l=tot;//对于每个被修改的位置,新建一个点。并将原来的值修改 insert(tree[v].l,i,mid,x,y,z); } else if (x>mid) { if (!bz) tree[++tot]=tree[tree[v].r],tree[v].r=tot;//对于每个被修改的位置,新建一个点。并将原来的值修改 insert(tree[v].r,mid+1,j,x,y,z); } else { if (!bz) tree[++tot]=tree[tree[v].l],tree[v].l=tot;insert(tree[v].l,i,mid,x,mid,z);//对于每个被修改的位置,新建一个点。并将原来的值修改 if (!bz) tree[++tot]=tree[tree[v].r],tree[v].r=tot;insert(tree[v].r,mid+1,j,mid+1,y,z);//对于每个被修改的位置,新建一个点。并将原来的值修改 } tree[v].data=max(tree[tree[v].l].data,tree[tree[v].r].data); } void find(int v,int i,int j,int x,int y) { if (i==x && j==y) {ans=max(ans,tree[v].data);return;} if (tree[v].lazy) down(v,i,j); int mid=(i+j)/2; if (y<=mid) find(tree[v].l,i,mid,x,y); else if (x>mid) find(tree[v].r,mid+1,j,x,y); else find(tree[v].l,i,mid,x,mid),find(tree[v].r,mid+1,j,mid+1,y); } int main() { scanf("%d",&n); g[1]=1; fo(i,1,n) scanf("%d",&a[i]); build(g[1],1,n); int ac;scanf("%d",&ac); for(;ac;ac--) { int x,y,z,yy; scanf("%d%d%d",&x,&y,&z); if (x==1) { scanf("%d",&yy); g[++tt]=++tot;//建立一个新的根节点 tree[tot]=tree[g[tt-1]]; insert(g[tt],1,n,y,z,yy); } if (x==2) { ans=-2147483647;find(g[tt],1,n,y,z); printf("%d\n",ans); } } }