周报

主席树

2020年4月5日

前置知识

可持久化：简单来说可持久化的数据结构是一种支持访问历史版本的数据结构，比如说我对这个数据结构经过若干次修改之后，依然可以访问以前某一次修改时的数据结构。

权值线段树：权值线段树相当于一个桶，可以维护区间里每个数个数出现的次数。一般某一个节点存的是对应的值出现的次数。具体操作跟线段树区别不是很大。可以用来求所有数的kth、查询某个数出现的总次数。

前缀和思想

用主席树解决区间kth问题

考虑到权值线段树只能求总区间内也就是[1..n]的kth，所以我们考虑对每一个数都建立一颗权值线段树。

比如说这一组数据：1 2 3 2 4 5

我们先建立一颗空树：

（黑色的是区间范围，红色的是范围内数的个数）

然后我们在1上新建一个树

全建完之后是这个样子：

然后我们可以发现，点x处的线段树表示的是区间[1,x]内的值的情况，点y处表示的是区间[1,y]内的值的情况。所以如果我们将这两颗线段树相减，得到的就是区间[x+1,y]的值的情况。

当然，在数组很大的情况下这样做显然是不行的。我们发现这些线段树上有很多的重复的点，所以可以对这些点加以利用。

比如说刚才加入值1的线段树可以改成这个样子：

换言之就是修改的时候动态开点，然后对需要修改的点同样新开点，不需要修改的还连到原来的点就行了。

kth参考代码：

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;

const int MAXN=5e5+5;
struct node{
	int dat,lc,rc;//dat存一共多少个
}t[MAXN<<5];
int tot,n,m,rt[MAXN],a[MAXN],Max,x,y,k;

void bt(int x,int l,int r){
	if (l==r){
		t[x].dat=0;
		return ;
	}
	int mid=(l+r)>>1;
	t[x].lc=++tot;
	t[x].rc=++tot;
	bt(t[x].lc,l,mid);
	bt(t[x].rc,mid+1,r);
}

void add(int x,int dat,int l,int r,int las){//修改
	t[x].dat=t[las].dat+1;
	if (l==r) return ;
	int mid=(l+r)>>1;
	if (dat<=mid){
		t[x].rc=t[las].rc;
		t[x].lc=++tot;
		add(t[x].lc,dat,l,mid,t[las].lc);
	}else{
		t[x].lc=t[las].lc;
		t[x].rc=++tot;
		add(t[x].rc,dat,mid+1,r,t[las].rc);
	}
}

int query(int las,int x,int l,int r,int dat){//查询
	int tmp1=t[t[x].lc].dat-t[t[las].lc].dat;
	int mid=(l+r)>>1;
	if (l==r) return l;
	if (dat<=tmp1){
		return query(t[las].lc,t[x].lc,l,mid,dat);
	}else{
		return query(t[las].rc,t[x].rc,mid+1,r,dat-tmp1);
	}
}

int main(){
	cin>>n;rt[0]=0;tot=0;
	for (int i=1;i<=n;i++) cin>>a[i],Max=max(Max,a[i]);
	bt(rt[0],1,Max);
	for (int i=1;i<=n;i++){
		rt[i]=++tot;
		add(rt[i],a[i],1,Max,rt[i-1]);
	}
	cin>>m;
	for (int i=1;i<=m;i++){
		cin>>x>>y>>k;
		cout<<query(rt[x-1],rt[y],1,Max,k)<<endl;
	} 
	return 0;
}

例题：Luogu P3567

Luogu P2633

Luogu P1801

Views: 154

发表评论