算法笔记——可持久化线段树

维护历史值

当要修改一个节点时，把跟他有关的线段树中所有节点舍弃，并建立新节点连接.

代码如下：

#include <bits/stdc++.h>
using namespace std;
const int N=1e6+5;
int n,m,a[N],root[N],top;
struct node
{
	int l,r,val;
}t[N*40];
int clone(int x)//新建节点
{
	top++;
	t[top]=t[x];
	return top;
}
int build(int x,int l,int r)//建树
{
	x=++top;
	if(l==r)
	{
		t[x].val=a[l];
		return top;
	}
	int mid=(l+r)>>1;
	t[x].l=build(t[x].l,l,mid);
	t[x].r=build(t[x].r,mid+1,r);
	return x;
}
int update(int u,int l,int r,int x,int val){
	u=clone(u);
	if(l==r){
		t[u].val=val;
		return u;
	}
	else{
		int mid=(l+r)>>1;
		if(x<=mid)
		{
			t[u].l=update(t[u].l,l,mid,x,val);
		}
		else
		{
			t[u].r=update(t[u].r,mid+1,r,x,val);
		}
	}
    return u;
}
int query(int u,int l,int r,int x)
{
	if(l==r){
		return t[u].val;
	}
	else{
		int mid=(l+r)>>1;
		if(x<=mid)return query(t[u].l,l,mid,x);
		else return query(t[u].r,mid+1,r,x);
	}
}
int main()
{
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;i++)scanf("%d",&a[i]);
	root[0]=build(0,1,n);
	for(int i=1,op,rt,x,y;i<=m;i++)
	{
		scanf("%d%d%d",&rt,&op,&x);
		if(op==1)
		{
			scanf("%d",&y);
			root[i]=update(root[rt],1,n,x,y);
		}
		else
		{
			printf("%d\n",query(root[rt],1,n,x));
			root[i]=root[rt];
		}
	}
	return 0;
}

求区间第k最值

先离散化数组.

再建立可持久化线段树，依次加入数组里每个数

利用前缀和，求第k最值.

#include <bits/stdc++.h>
using namespace std;
const int N=2e5+5;
int n,ind[N],a[N],m,len,rt[N];
int tot;
int ls[N<<5],rs[N<<5],sum[N<<5];
int getid(int x)
{
	return lower_bound(ind+1,ind+len+1,x)-ind;
}
int build(int l,int r)
{
	int root=++tot;
	if(l==r)return root;
	int mid=(l+r)>>1;
	ls[root]=build(l,mid);
	rs[root]=build(mid+1,r);
	return root; 
}
int update(int k,int l,int r,int root)
{
	int dir=++tot;
	ls[dir]=ls[root],rs[dir]=rs[root],sum[dir]=sum[root]+1;//多了一个数
	if(l==r)
	{
		return dir;
	}
	int mid=(l+r)>>1;
	if(k<=mid)
	{
		ls[dir]=update(k,l,mid,ls[dir]);
	}
	else
	{
		rs[dir]=update(k,mid+1,r,rs[dir]);
	}
	return dir;
}
int query(int u,int v,int l,int r,int k)
{
	int x=sum[ls[v]]-sum[ls[u]];//求左子树有多少种数
	if(l==r)
	{
		return l;
	}
	int mid=(l+r)>>1;
	if(k<=x)//在这个区间中，第k最值小于等于左子树数的总数
	{
		return query(ls[u],ls[v],l,mid,k);
	}
	else
	{
		return query(rs[u],rs[v],mid+1,r,k-x);
	}
}
void init()
{
	cin>>n>>m;
	for(int i=1;i<=n;i++)
	{
		cin>>a[i];
	}
	memcpy(ind,a,sizeof(ind));
	sort(ind+1,ind+n+1);
	len=unique(ind+1,ind+n+1)-ind-1;//离散化
	rt[0]=build(1,len);
	for(int i=1;i<=n;i++)
	{
		rt[i]=update(getid(a[i]),1,len,rt[i-1]);
	}
}
int l,r,k;
void work()
{
	while(m--)
	{
		cin>>l>>r>>k;
		cout<<ind[query(rt[l-1],rt[r],1,len,k)]<<'\n';
	}
}
int main()
{
	init();
	work();
	return 0;
}