欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

主席树 单点更新 区间第k大

程序员文章站 2024-03-02 22:03:34
...

话不多说直接写(好像咕了好久了)----2019.5.3

主席数的概念

主席树又叫可持续性线段树,它可以保存区间各个修改时段的状态。它通过在原树上不断附加单链来实现logn复杂度的修改和记忆,子树间的联系不再是乘2或乘2加1而是通过直接存数组下标来实现保存(类似指针)。对不同时段的搜索也是依靠记录该时段根的下标来实现的。

讲一下主席树的搜索过程:
首先确定此次要搜索的是哪次的状态,确定是左子树还是右子树,沿着它记录的下标前进(下标可能走向任意方向),直到走到具体点为止。

luoguP3919

#include <iostream>
#include <cstdio>
using namespace std;
int n,m,cnt;//用内存池法建树,用cnt辅助建 
const int maxn = 1e6+10;

struct node{
	int lson,rson,num;//左子树,右子树的数组下标,维护的值 
}infor[20*maxn];//空间需求大 
int root[maxn];

void build_tree(int &p,int l,int r){
	p=++cnt;//p为当前下标,持续增大 
	if(l==r){
		scanf("%d",&infor[p].num);
		return;
	}
	int mid=(l+r)/2;
	build_tree(infor[p].lson,l,mid);//利用引用对左右子树进行赋值 
	build_tree(infor[p].rson,mid+1,r);
}

void update(int &p,int old,int tag,int l,int r,int val){
	p=++cnt;//更新就建新树 
	infor[p]=infor[old];//集体复制 
	if(l==r){
		infor[p].num=val;//找到定点,更新 
		return;
	}
	int mid=(l+r)/2;
	if(tag<=mid){
		update(infor[p].lson,infor[p].lson,tag,l,mid,val);//向目标方向更新,另一方向不变,后续检索时检索到原树上(形参里两个相同的值,第一个用于更新,第二个用于访问当前值,与指针的方式类似) 
	}
	else{
		update(infor[p].rson,infor[p].rson,tag,mid+1,r,val);
	}
}

void query(int p,int tag,int l,int r){
	if(l==r){
		printf("%d\n",infor[p].num);
		return;
	}
	int mid=(l+r)/2;
	if(tag<=mid){
		query(infor[p].lson,tag,l,mid);
	}
	else{
		query(infor[p].rson,tag,mid+1,r);
	}
}

int main(){
	scanf("%d%d",&n,&m);
	build_tree(root[0],1,n);
	for(int i=1;i<=m;i++){
		int ti,form;
		scanf("%d%d",&ti,&form);
		if(form==1){
			int tag,val;
			scanf("%d%d",&tag,&val);
			update(root[i],root[ti],tag,1,n,val);//每次在指定的条件下做更新,用引用更新根的下标 
		}
		else{
			int tag;
			scanf("%d",&tag);
			query(root[ti],tag,1,n);
			root[i]=root[ti]; 
		}
	}
	return 0;
} 

poj 区间第k大

#include <iostream>
#include <algorithm>
#include <vector>
#include <cstdio>
using namespace std;
const int maxn = 1e5+10;
struct node{
	int lson,rson,sum;//sum维护在当前插入的所有值中,总大小排序在第l到第r之间的有多少个 
}infor[40*maxn];
int n,m,cnt,inp[maxn],root[maxn];
vector<int> v;

int getpos(int a){//离散化找值 
	return lower_bound(v.begin(),v.end(),a)-v.begin()+1;
}

void update(int &p,int old,int tag,int l,int r){//建树 
	p=++cnt;
	infor[p]=infor[old];
	infor[p].sum++;
	if(l==r){
		return;
	}
	int mid=(l+r)/2;
	if(mid>=tag){
		update(infor[p].lson,infor[p].lson,tag,l,mid);
	}
	else{
		update(infor[p].rson,infor[p].rson,tag,mid+1,r);
	}
}

void query(int l,int r,int x,int y,int k){//x,y是在主席树上移动的方向,l,r是当前所查区间 
	if(l==r){
		printf("%d\n",v[l-1]);
		return;
	}
	int now=infor[infor[y].lson].sum-infor[infor[x].lson].sum;//出现的数目 
	int mid=(l+r)/2;
	if(now>=k){//向左或右搜索 
		query(l,mid,infor[x].lson,infor[y].lson,k);//在当前左区间,总排序大小在第l到第mid的已经大于等于k了,所以第k大一定在子区间 
	}
	else{
		query(mid+1,r,infor[x].rson,infor[y].rson,k-now);//左子树的sum小于k,即在左子树找不到第k大,那么就应该在右子树找第k-左sum大的值 
	}
}

int main(){
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;i++){
		scanf("%d",&inp[i]);
		v.push_back(inp[i]);
	}
	sort(v.begin(),v.end());
	v.erase(unique(v.begin(),v.end()),v.end());//离散化 
	for(int i=1;i<=n;i++){
		update(root[i],root[i-1],getpos(inp[i]),1,n);//每加一个值更新一次主席树,在原树的基础上把这个值加进去。与它相关的每一个区间值都加1,表示此区间大小范围内多了一个数 
	}
	for(int i=0;i<m;i++){
		int l,r,k;
		scanf("%d%d%d",&l,&r,&k);
		query(1,n,root[l-1],root[r],k);//类似前缀和查法,在[l,r]之间查 
	}
	return 0;
}

这个博客写的草率只是因为我懒,而且菜,毕竟看了一天才看懂这些问题。这个博客主要是为了自己以后查模板用,想具体学的话还是另找博客吧。(手动狗头)