可持久化线段树 学习笔记

• 板子题1
• 算法解析
• 板子题2
• 算法解析

板子题1

题目链接
你需要维护这样的一个长度为 \(n\) 的数组，支持如下几种操作（操作次数为 \(m\)）：

• 在某个历史版本上修改某一个位置上的值。
• 访问某个历史版本上的某一位置的值。

此外，每进行一次操作（对于操作 \(2\)，即为生成一个完全一样的版本，不作任何改动），就会生成一个新的版本。版本编号即为当前操作的编号（从 \(1\) 开始编号，版本 \(0\) 表示初始状态数组）
数据范围： \(n,m\le 2\times 10^5\)。

算法解析

考虑使用线段树。
首先我们看一下线段树长什么样：

我们发现如果我们单点修改/区间修改的话，我们发现最多修改 \(\log n\) 个节点的数值，也就是一条链或者是两条链。
也就是长这个样子：

由于线段树父认子子不认父，所以可以直接新开一条链，然后存下每个版本的根。
这样空间复杂度 \(\Theta(m\log n)\)，时间复杂度单次查询/修改都是 \(\Theta(\log n)\)。
代码：

#include
#define db double
#define gc getchar
#define pc putchar
#define U unsigned
#define ll long long
#define ld long double
#define ull unsigned long long
#define Tp template
#define Me(a,b) memset(a,b,sizeof(a))
Tp _T mabs(_T a){ return a>0?a:-a; }
Tp _T mmax(_T a,_T b){ return a>b?a:b; }
Tp _T mmin(_T a,_T b){ return a9) print(x/10); pc((x%10)+48); return; }
#define EPS (1e-7)
#define INF (0x7fffffff)
#define LL_INF (0x7fffffffffffffff)
#define maxn 1000039
#define maxm maxn*25
#define MOD
#define Type int
#ifndef ONLINE_JUDGE
//#define debug
#endif
using namespace std;
Type read(){
	char c=gc(); Type s=0; int flag=0;
	while((c<'0'||c>'9')&&c!='-') c=gc(); if(c=='-') c=gc(),flag=1;
	while('0'<=c&&c<='9'){ s=(s<<1)+(s<<3)+(c^48); c=gc(); }
	if(flag) return -s; return s;
}
int n,K,T,opt,V,X,C,arr[maxn],root[maxn];
struct Node{ int ls,rs,val; } a[maxm];
int build(int l,int r){
	int rt=++K; if(l==r){ a[rt].val=arr[l]; return rt; }
	int mid=(l+r)>>1; a[rt].ls=build(l,mid);
	a[rt].rs=build(mid+1,r); return rt;
}
int update(int l,int r,int rt){
	a[++K]=a[rt]; rt=K; if(l==r){ a[rt].val=C; return rt; } int mid=(l+r)>>1;
	if(X<=mid) a[rt].ls=update(l,mid,a[rt].ls); else a[rt].rs=update(mid+1,r,a[rt].rs);
	return rt;
}
int query(int l,int r,int rt){
	if(l==r) return a[rt].val; int mid=(l+r)>>1;
	if(X<=mid) return query(l,mid,a[rt].ls);
	else return query(mid+1,r,a[rt].rs);
}
int main(){
	n=read(); T=read(); int i; for(i=1;i<=n;i++) arr[i]=read(); root[0]=build(1,n);
	for(i=1;i<=T;i++){
		V=read(); opt=read(); X=read();
		if(opt==1){ C=read(); root[i]=update(1,n,root[V]); }
		else { root[i]=root[V]; print(query(1,n,root[V])),pc('\n'); }
	}
	return 0;
}

板子题2

题目链接
主席树模板——静态区间第 \(k\) 小。
如题，给定 \(n\) 个整数构成的序列 \(a\)，将对于指定的闭区间 \([l,r]\) 查询其区间内的第 \(k\) 小值，查询 \(m\) 次。
数据范围 \(n,m\le 10^5，a_i\le 10^9\)。

算法解析

严格说，主席树的正名为可持久化权值线段树。

首先需要了解什么是权值线段树。
权值线段树指的就是点对应一个区间，例如在此题中 \([l,r]\) 就代表 \([l,r]\) 这个区间内有几个数字。

我们发现，如果把这些序列的数字依次加入权值线段树，那么不难发现版本 \(i\) 对应的是序列前 \(i\) 个数字的权值线段树，利用差分就能得到序列中区间 \([l,r]\) 中值为 \([l',r']\) 中的数字个数。
然后线段树上二分即可。
代码：

#include
#define db double
#define gc getchar
#define pc putchar
#define U unsigned
#define ll long long
#define ld long double
#define ull unsigned long long
#define Tp template
#define Me(a,b) memset(a,b,sizeof(a))
Tp _T mabs(_T a){ return a>0?a:-a; }
Tp _T mmax(_T a,_T b){ return a>b?a:b; }
Tp _T mmin(_T a,_T b){ return a9) print(x/10); pc((x%10)+48); return; }
#define EPS (1e-7)
#define INF (0x7fffffff)
#define LL_INF (0x7fffffffffffffff)
#define maxn 1000039
#define maxm maxn*25
#define MOD
#define Type int
#ifndef ONLINE_JUDGE
//#define debug
#endif
using namespace std;
Type read(){
	char c=gc(); Type s=0; int flag=0;
	while((c<'0'||c>'9')&&c!='-') c=gc(); if(c=='-') c=gc(),flag=1;
	while('0'<=c&&c<='9'){ s=(s<<1)+(s<<3)+(c^48); c=gc(); }
	if(flag) return -s; return s;
}
int n,K,T,opt,V,X,C,arr[maxn],root[maxn];
struct Node{ int ls,rs,val; } a[maxm];
int build(int l,int r){
	int rt=++K; if(l==r){ a[rt].val=arr[l]; return rt; }
	int mid=(l+r)>>1; a[rt].ls=build(l,mid);
	a[rt].rs=build(mid+1,r); return rt;
}
int update(int l,int r,int rt){
	a[++K]=a[rt]; rt=K; if(l==r){ a[rt].val=C; return rt; } int mid=(l+r)>>1;
	if(X<=mid) a[rt].ls=update(l,mid,a[rt].ls); else a[rt].rs=update(mid+1,r,a[rt].rs);
	return rt;
}
int query(int l,int r,int rt){
	if(l==r) return a[rt].val; int mid=(l+r)>>1;
	if(X<=mid) return query(l,mid,a[rt].ls);
	else return query(mid+1,r,a[rt].rs);
}
int main(){
	n=read(); T=read(); int i; for(i=1;i<=n;i++) arr[i]=read(); root[0]=build(1,n);
	for(i=1;i<=T;i++){
		V=read(); opt=read(); X=read();
		if(opt==1){ C=read(); root[i]=update(1,n,root[V]); }
		else { root[i]=root[V]; print(query(1,n,root[V])),pc('\n'); }
	}
	return 0;
}