可持久化线段树

可持久化就是支持维护不同时间下的版本的数据结构啦。

那么可持久化线段树能干什么很显然了。

可持久化线段树又叫主席树，因为来历大家都知道就不多说了。

那么就直接讲核心操作了，就是克隆节点。

克隆节点

就是在修改的时候（或者维护多棵有公共节点的线段树时）使用。把有变化的节点新建，由于每次如果进行单点修改是修改一条长为 $log\ n$ 的链所以空间复杂度是 $O((n+m)log\ n)$ 的（m是操作数）。

直接把修改前的节点克隆过来即可。回溯时 $pushup$ 即可。

单点修改示例：

int modify(int i,int p,int val){
		t[++tot]=t[i];
		i=tot;
		if(p==t[i].l&&t[i].r==p){
			t[i].val=val;
			return i;
		}
		if(p<=t[i].mid) t[i].lc=modify(t[i].lc,p,val);
		if(t[i].mid+1<=p) t[i].rc=modify(t[i].rc,p,val);
		return i;
	}

例题分析

可持久化线段树 1

模板题，我就直接给代码了，与线段树的区别就只是有多个版本。（不同版本我们用不同根节点来维护）

#include<bits/stdc++.h>
using namespace std;
#define file(a) freopen(#a".in","r",stdin),freopen(#a".out","w",stdout)
#define LL long long
#define N 1000000+3
#define M 1000000+3
#define LOG 20+3
inline int read(){
	int s=0,f=1;
	char ch=getchar();
	while(ch<'0'||'9'<ch) {if(ch=='-') f=-1;ch=getchar();}
	while('0'<=ch&&ch<='9') {s=s*10+(ch^48);ch=getchar();}
	return s*f;
}
int n,m;
int rt[M];
int a[N];
struct SegTree{
	int tot;
	struct Node{
		int l,r,mid;
		int lc,rc,val;
	}t[(N+M)*LOG];
	SegTree(){
		tot=0;
	}
	int build(int i,int l,int r){
		//printf("%d[%d,%d]\n",i,l,r);
		t[i].l=l;t[i].r=r;t[i].mid=(l+r)>>1;
		t[i].val=0;
		if(l==r){
			t[i].val=a[l];
			return i;
		} 
		t[i].lc=build(++tot,l,t[i].mid);
		t[i].rc=build(++tot,t[i].mid+1,r);
		return i;
	}
	int modify(int i,int p,int val){
		t[++tot]=t[i];
		i=tot;
		if(p==t[i].l&&t[i].r==p){
			t[i].val=val;
			return i;
		}
		if(p<=t[i].mid) t[i].lc=modify(t[i].lc,p,val);
		if(t[i].mid+1<=p) t[i].rc=modify(t[i].rc,p,val);
		return i;
	}
	int query(int i,int p){
		if(p==t[i].l&&t[i].r==p){
			return t[i].val;
		} 
		int res=0;
		if(p<=t[i].mid) res+=query(t[i].lc,p);
		if(t[i].mid+1<=p) res+=query(t[i].rc,p);
		return res;
	} 
}t;
int main(){
	n=read();m=read();
	for(int i=1;i<=n;++i){
		a[i]=read();
	}
	rt[0]=t.build(++t.tot,1,n);
	for(int i=1;i<=m;++i){
		int tim=read(),opt=read(),p=read();
		if(opt==1){
			int val=read();
			rt[i]=t.modify(rt[tim],p,val);
		}else{
			printf("%d\n",t.query(rt[tim],p));
			rt[i]=rt[tim];
		}
	}
	return 0;
}