可持久化线段树(主席树)的某个神仙写法

前言

快要NOIP了,写点板子~~放松心情~~复习一下
之前老师讲过主席树,but我~~是抄的板子~~没好好写,导致现在看我之前的代码有一种看不懂的感觉.于是我就从定义开始,重学了一遍主席树.

正文

主席树,全名可持久化线段树,是利用线段树每次单点修改都只会影响一条链上的节点这个机制进行可持久化的线段树.每次修改都会影响到根节点,所以我们只需要记录根节点就可以记录每个版本.(上面的纯属我个人理解,~~不懂的到网上自己查~~)
而我就按照这个思路写了一份非常神仙的代码.
这份代码神仙的地方有很多,但我认为最主要的还是两点:(1).我把build吞了;(2).我的update(对应代码中的change)是void,把k改成了引用.

CPP

#include<bits/stdc++.h>
using namespace std;

const int N=2e5+10;
struct X{
	int v,ls,rs;
}tr[N*40];
int cnt,root[N];
void push_up(int k){
	tr[k].v=tr[tr[k].ls].v+tr[tr[k].rs].v;
}
void change(int &k,int l,int r,int x,int v,X last){
	if(!k)k=++cnt;
	tr[k]=last;
	if(l==r){
		tr[k].v+=v;
		return;
	}
	int mid=l+r>>1;
	if(x<=mid){
		int ls=tr[k].ls;
		tr[k].ls=0;
		change(tr[k].ls,l,mid,x,v,tr[ls]);
	}
	else{
		int rs=tr[k].rs;
		tr[k].rs=0;
		change(tr[k].rs,mid+1,r,x,v,tr[rs]);
	}
	push_up(k);
}
int t1,t2;
int qest(int l,int r,int v){
	if(l==r)return l;
	int sum=tr[tr[t2].ls].v-tr[tr[t1].ls].v;
	int mid=l+r>>1;
	if(v<=sum){
		t1=tr[t1].ls;
		t2=tr[t2].ls;
		return qest(l,mid,v);
	}
	t1=tr[t1].rs;
	t2=tr[t2].rs;
	return qest(mid+1,r,v-sum);
}
int n,m,a[N],o[N],len;
int main(){
    ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    cin>>n>>m;
    for(int i=1,x;i<=n;i++){
    	cin>>a[i];
    	o[i]=a[i];
	}
	sort(o+1,o+n+1);
	len=unique(o+1,o+n+1)-o-1;
	for(int i=1;i<=n;i++){
		a[i]=lower_bound(o+1,o+len+1,a[i])-o;
		change(root[i],1,len,a[i],1,tr[root[i-1]]);
	}
	int l,r,k;
	while(m--){
		cin>>l>>r>>k;
		t1=root[l-1];
		t2=root[r];
		cout<<o[qest(1,len,k)]<<'\n';
	}
    return 0;
}

后记

我看了一下大佬们的代码,找了半天也没找到和我思路相同的.这时我才意识到我的代码有多奇葩,于是发篇文章纪念一下.

可持久化线段树(主席树)的某个神仙写法

文章操作

前言

正文

后记

相关推荐

评论

可持久化线段树(主席树)的某个神仙写法