可持久化线段树(主席树)

我

终于

学会了

人生中第

一个可持久

化的数据结构

可持久化线段树

首先我一直搞不清可持久化线段树和主席树之间到底有什么联系，两者到底是不是同一个东西？

来看看大佬们的回答：

个人比较赞同的是：主席树是可持久化线段树的真子集，即主席树是权值线段树的可持久化，而可持久化线段树则是对所有线段树的可持久化。

好了，进入正题：

什么是可持久化线段树？

对于一棵线段树，我们不时的对他进行修改和查询，那么我们每次一次修改之后就会得到一棵新的结构，但是当我们需要查询某一个历史版本的区间信息时，该怎么办呢？

如果我没猜错，你的做法应该是将每一个版本复制之后记录下来，那么对于有 $m$ 次修改和查询的线段树，在一定数据范围肯定 MLE+TLE。

有没有节省空间的方法？？？

不用完全复制一个线段树来保存历史版本，对于新修改的节点或者区间，只需要添加一条或者几条从根节点到修改节点的树链即可，其他的节点不变，新版本的节点对应与上一版本没有修改的节点建立关系连接。

比如说初始版本是这样：

如果我们想要修改一下 $[1,1]$ 区间的值为 $14$ ，该怎么办呢？

按照刚才的定义，我们其他区间不变，直接复制第 $1$ 个版本，而包含 $[1,1]$ 的区间则需要新建赋值。

这样大幅节省了空间。每次创建一个新的版本时，只要新建 $log _2 n$ 个节点，也就是只保存从新版本的根节点到更新的那一个叶子节点的路径，不在此路径上的左/右儿子只要接原版本对应区间的对应儿子。可以保证，从对应版本的根节点一定能访问到对应叶子节点的值。

来看一个简单的例题：

例 $1$

给定一个长度为 $n$ 的整数数组 $A[1],A[2],…,A[n](<-10 ^9\le A[i]\le 10 ^9>)$ ，和 $m$ 个操作：

操作 $1$ ：1 i x 把 $A[i]$ 修改成 $x(-10 ^9\le x\le 10 ^9)$ ；

操作 $2$ ：2 t i j 查询前 $t$ 次操作后的序列中连续子序列 $A[i]..A[j]$ 中的最小值， $t$ 从 $0$ 开始计数。

很明显这是一个可持久化线段树的裸题，只用维护一个普通查询最小值的线段树即可，支持单点修改。

定义 rt[i] 为第 i 个版本的根节点编号。

建树：

void pushup(int rt)
{
	tree[rt]=min(tree[ls[rt]],tree[rs[rt]]);
}
void build(int l,int r,int &rt)
{
	rt=++num;//新的根节点
	if(l==r)
	{
		tree[rt]=a[l];
		return ;
	}
	int mid=(l+r)>>1;
	build(lson);
	build(rson);
	pushup(rt);
}

单点修改：

void update(int x,int val,int l,int r,int rt)
{
	if(l==r)
	{
		tree[++num]=val;
		return ;
	}
	int mid=(l+r)>>1;
	if(x<=mid)
	{
		update(x,val,lson);
		num++;
		ls[num]=num-1;//左边修改，新建左儿子
		rs[num]=rs[rt];//复制右边
	}
	else
	{
		update(x,val,rson);
		num++;
		rs[num]=num-1;//同理
		ls[num]=ls[rt];
	}
	pushup(num);
}
···
if(op==1)
{
	sum++;
	scanf("%d%d",&l,&x);
	update(l,x,1,maxn,root[sum-1]);//以上一个版本为基础修改
	root[sum]=num;//新的版本
}

查询最值：

int found(int L,int R,int l,int r,int rt)
{
	if(L<=l&&r<=R)
		return tree[rt];
	int ans=INF;
	int mid=(l+r)>>1;
	if(L<=mid)
		ans=min(ans,found(L,R,lson));
	if(R>mid)
		ans=min(ans,found(L,R,rson));
	return ans;
}
···
if(op==2)
{
	sum++;
	scanf("%d%d%d",&t,&l,&r);
	printf("%d\n",found(l,r,1,maxn,root[t]));//查询
	root[sum]=root[sum-1];//不修改，直接复制
}

注意可持续化线段树大概要开 $n$ 的 $32$ 倍，即 $n<<5$ 。

#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<cmath>
#include<algorithm>
#define lson l,mid,ls[rt]
#define rson mid+1,r,rs[rt]
#define INF 1e9
using namespace std;
const int maxn=2e6+101;
int n,m,num,sum;
int a[maxn],root[maxn];
int tree[maxn<<2],ls[maxn<<2],rs[maxn<<2];
void pushup(int rt)
{
	tree[rt]=min(tree[ls[rt]],tree[rs[rt]]);
}
void build(int l,int r,int &rt)
{
	rt=++num;
	if(l==r)
	{
		tree[rt]=a[l];
		return ;
	}
	int mid=(l+r)>>1;
	build(lson);
	build(rson);
	pushup(rt);
}
void update(int x,int val,int l,int r,int rt)
{
	if(l==r)
	{
		tree[++num]=val;
		return ;
	}
	int mid=(l+r)>>1;
	if(x<=mid)
	{
		update(x,val,lson);
		num++;
		ls[num]=num-1;//左边修改，新建左儿子
		rs[num]=rs[rt];//复制右边
	}
	else
	{
		update(x,val,rson);
		num++;
		rs[num]=num-1;
		ls[num]=ls[rt];
	}
	pushup(num);
}
int found(int L,int R,int l,int r,int rt)
{
	if(L<=l&&r<=R)
		return tree[rt];
	int ans=INF;
	int mid=(l+r)>>1;
	if(L<=mid)
		ans=min(ans,found(L,R,lson));
	if(R>mid)
		ans=min(ans,found(L,R,rson));
	return ans;
}
int main()
{
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;i++)
		scanf("%d",&a[i]);
	build(1,maxn,root[0]);
	for(int i=1;i<=m;i++)
	{
		int op,t,l,r,x;
		scanf("%d",&op);
		if(op==1)
		{
			sum++;
			scanf("%d%d",&l,&x);
			update(l,x,1,maxn,root[sum-1]);
			root[sum]=num;//新的版本
		}
		else
		{
			sum++;
			scanf("%d%d%d",&t,&l,&r);
			printf("%d\n",found(l,r,1,maxn,root[t]));
			root[sum]=root[sum-1];//不修改，直接复制
		}
	}
	return 0;
}

例 $2$

静态区间第 $k$ 小：

给定 $n$ 个整数构成的序列，将对于指定的闭区间查询其区间内的第 $k$ 小值。

如果数据范围较小的话，可以直接离散化加权值线段树，用离线做法排序依次解决，可惜这道题数据范围较大。

这下我们就要用到可持久化线段树，维护一个权值线段树，即主席树。

对于一列数，可以对于每个点 $i$ 都建一棵权值线段树，维护 $1\sim i$ 这些数，每个不同的数出现的个数(权值线段树以值域作为区间)。

现在， $n$ 棵线段树就建出来了，第 $i$ 棵线段树代表 $1\sim i$ 这个区间。

第 $x$ 棵线段树减去第 $y$ 棵线段树会发生什么？

第 $x$ 棵线段树代表的区间是 $[1,x]$ 。

第 $y$ 棵线段树代表的区间是 $[1,y]$ 。

两棵线段树一减，设 $x>y$ ， $[1,x]−[1,y]=[y+1,x]$ 。

所以这两棵线段树相减可以产生一个新的区间对应的线段树！

这就是主席树的一个核心思想：前缀和思想。

#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<cmath>
#include<algorithm>
#define INF 1e9
#define lson l,mid,ls[rt]
#define rson mid+1,r,rs[rt]
using namespace std;
const int maxn=2e5+101;
int n,m,num,sum,last,a[maxn];
int tree[maxn<<5],root[maxn];
int ls[maxn<<5],rs[maxn<<5];
void pushup(int rt)
{
	tree[rt]=tree[ls[rt]]+tree[rs[rt]];
}
void build(int l,int r,int &rt)
{
	rt=++num;
	if(l==r)
	{
		tree[rt]=a[l];
		return ;
	}
	int mid=(l+r)>>1;
	build(lson);
	build(rson);
}
void update(int x,int val,int l,int r,int rt)
{
	if(l==r)
	{
		tree[++num]=tree[rt]+val;
		return ;
	}
	int mid=(l+r)>>1;
	if(x<=mid)
	{
		update(x,val,lson);
		num++;
		ls[num]=num-1;
		rs[num]=rs[rt];
	}
	else
	{
		update(x,val,rson);
		num++;
		rs[num]=num-1;
		ls[num]=ls[rt];
	}
	pushup(num);
}
int kth(int L,int R,int k,int l,int r)
{
	if(l==r)
		return l;
	int mid=(l+r)>>1;
	int t=tree[ls[R]]-tree[ls[L]];
	if(t>=k)
		return kth(ls[L],ls[R],k,l,mid);
	else
		return kth(rs[L],rs[R],k-t,mid+1,r);
}
int main()
{
	scanf("%d%d",&n,&m);
	build(0,maxn,root[0]);
	for(int i=1;i<=n;i++)
	{
		scanf("%d",&a[i]);
		sum++;
		update(a[i],1,0,maxn,root[sum-1]);
		root[sum]=num;//建树
	}
	for(int i=1;i<=m;i++)
	{
		int x,y,k;
		scanf("%d%d%d",&x,&y,&k);
		last=kth(root[x-1],root[y],k,0,maxn);//前缀和思想！
		printf("%d\n",last);
	}
	return 0;
}

例 $3$

在例 $2$ 的原题上在加入一个操作：查询 $A[x]…A[y]$ 中属于区间 $[a,b]$ 的元素个数。

一样的，用主席树搞一下就可以了。

给出查询元素个数代码：

int find(int L,int R,int l,int r,int a,int b)//在[a,b]中查找属于[L,R]的元素个数
{
	if(l>R||r<L)
		return 0;
	if(L<=l&&r<=R)
		return tree[b]-tree[a];
	int mid=(l+r)>>1;
	return find(L,R,l,mid,ls[a],ls[b])+find(L,R,mid+1,r,rs[a],rs[b]);
}

例 $4$

对于一个长为 $n$ 的数组 $A[i]$ ，每次询问 $A[x]..A[y]$ 中小于 $v$ 的最大值。

主席树啊。

直接把区间内小于 $v$ 的个数求出来，再查询一次第 $k$ 小值即可，注意离散化。

#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<cmath>
#include<algorithm>
#define INF 1e9
#define lson l,mid,ls[rt]
#define rson mid+1,r,rs[rt]
using namespace std;
const int maxn=2e5+101;
int n,m,a[maxn],b[maxn],cnt;
int num,sum,root[maxn],tree[maxn<<5];
int ls[maxn<<5],rs[maxn<<5];
void pushup(int rt)
{
	tree[rt]=tree[ls[rt]]+tree[rs[rt]];
}
void build(int l,int r,int &rt)
{
	rt=++num;
	if(l==r)
		return ;
	int mid=(l+r)>>1;
	build(lson);
	build(rson);
}
void update(int x,int val,int l,int r,int rt)
{
	if(l==r)
	{
		tree[++num]=tree[rt]+val;
		return ;
	}
	int mid=(l+r)>>1;
	if(x<=mid)
	{
		update(x,val,lson);
		num++;
		ls[num]=num-1;
		rs[num]=rs[rt];
	}
	else
	{
		update(x,val,rson);
		num++;
		rs[num]=num-1;
		ls[num]=ls[rt];
	}
	pushup(num);
}
int kth(int L,int R,int k,int l,int r)
{
	if(l==r)
		return l;
	int mid=(l+r)>>1;
	int t=tree[ls[R]]-tree[ls[L]];
	if(t>=k)
		return kth(ls[L],ls[R],k,l,mid);
	else
		return kth(rs[L],rs[R],k-t,mid+1,r);
}
int find(int L,int R,int x,int l,int r)//在[L,R]中查找比x小的个数
{
	if(l==r)
		return 0;
	int mid=(l+r)>>1;
	if(x<=mid)
		return find(ls[L],ls[R],x,l,mid);
	else
		return tree[ls[R]]-tree[ls[L]]+find(rs[L],rs[R],x,mid+1,r);
}
int main()
{
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;i++)
	{
		scanf("%d",&a[i]);
		b[i]=a[i];
	}
	sort(b+1,b+n+1);
	cnt=unique(b+1,b+n+1)-b-1;
	build(0,maxn,root[0]);
	for(int i=1;i<=n;i++)
	{
		int q=lower_bound(b+1,b+cnt+1,a[i])-b;
		sum++;
		update(q,1,0,maxn,root[sum-1]);
		root[sum]=num;
	}
	for(int i=1;i<=m;i++)
	{
		int x,y,v;
		scanf("%d%d%d",&x,&y,&v);
		int rv=lower_bound(b+1,b+cnt+1,v)-b;
		int ans=find(root[x-1],root[y],rv,0,maxn);
		if(!ans)
			printf("None\n");
		else
			printf("%d\n",b[kth(root[x-1],root[y],ans,0,maxn)]);
	}
	return 0;
}

_{剩下的先咕咕}

什么是可持久化线段树？

例 111

例 222

例 333

例 444

例 $1$

例 $2$

例 $3$

例 $4$