初探fhq treap [alpha]

也是平衡树大家族的一员．

　参考资料

https://www.cnblogs.com/Axjcy/p/9475285.htm

https://www.jvruo.com/archives/375/#FHQ-Treap

https://wenku.baidu.com/view/a5f6fefe0066f5335a8121fa.html

https://blog.csdn.net/CABI_ZGX/article/details/79963427

普通平衡树　

题目链接

下面放两个代码吧，是不同的代码风格

个人更喜欢第一个版本的代码

代码version1

// ac
// 104 普通平衡树
#include <bits/stdc++.h>
using namespace std;
#define inc(i,a,b) for(int i=a;i<=b;i++)
#define dec(i,a,b) for(int i=a;i>=b;i--)
#define ll long long 
#define mst(a,b) memset(a,b,sizeof a)
#define pb push_back
inline int read(){
	char ch=getchar();int f=1,x=0;
	while(!isdigit(ch)) { if(ch=='-') f=-1;ch=getchar();}
	while(isdigit(ch)){ x=x*10+ch-'0';ch=getchar();}
	return f*x;
}


//by Sshwy
namespace RA{
	int rnd(int p){return 1ll*rand()*rand()%p;}
	int rnd(int L,int R){return rnd(R-L+1)+L;}
}

int n;
const int SZ = 5e5+5;
// fhq treap 的模板
template<class T>
struct Treap{
	int root,tot;
	int mem[SZ],memp;
	int lc[SZ],rc[SZ],sz[SZ];
	unsigned int rnd[SZ];

	T val[SZ];

	void clear(){
		fill(lc,lc+tot+1,0);
		fill(rc,rc+tot+1,0);
		fill(sz,sz+tot+1,0);
		root=tot=0;
	}

	Treap(){
		root=tot=0;
		srand(clock()+time(0));
		val[0] = 0;
	}

	inline void pushup(int u){
		sz[u] = sz[lc[u]]+sz[rc[u]]+1;

	}

	void split(int u,const int left_size,int &x,int &y){
		if(!u)return x=y=0,void();
		if(sz[lc[u]]+1<=left_size)x=u,split(rc[u],left_size-sz[lc[u]]-1,rc[u],y);
		else y=u,split(lc[u],left_size,x,lc[u]);
		pushup(u);
	}


	//按住权值拆分为两颗子树
	void split_by_val(int now,const T k,int &x,int &y){
		if(!now) return x=y=0,void();
		if(val[now]<=k) x=now,split_by_val(rc[now],k,rc[now],y);
		else y=now,split_by_val(lc[now],k,x,lc[now]);
		pushup(now);

	}

	//按照排名拆分成两颗子树
	void split_by_rank(int now,int k,int &x,int &y){
		if(!now) return x=y=0,void();
		if(sz[lc[now]]+1<=k) x=now,split_by_rank(rc[now],k-sz[lc[now]]-1,rc[now],y);
		else y=now,split_by_rank(lc[now],k,x,lc[now]);
		pushup(now);
	}

	//x,y两个子树,且所有的节点的值都小于y的所有节点的值
	//随机权重以小根堆的形式存储
	int merge(int x,int y){//x<y
		if(!x||!y)return x+y;
		//if(rand()%(sz[x]+sz[y])<sz[x])return rc[x]=merge(rc[x],y), pushup(x), x;
		if(rnd[x]<rnd[y])return rc[x]=merge(rc[x],y), pushup(x), x;
		else return lc[y]=merge(x,lc[y]), pushup(y), y;
	}


	void insert(T v){
		int a,b,u=memp?mem[memp--]:++tot;
		val[u]=v;
		sz[u]=1;
		rnd[u]=rand();
		split_by_val(root,v,a,b);
		root=merge(merge(a,u),b);
	}

	void remove(T x){
		int a,b,c,d,e,f;
		split_by_val(root,x,a,b);
		split_by_val(a,x-1,c,d);
		split_by_rank(d,1,e,f);
		root=merge(merge(c,f),b);
	}


	int findRank(T x){
		int a,b,c;
		split_by_val(root,x-1,a,b);
		c=sz[a]+1;
		root=merge(a,b);
		return c;
	}

	T findK(int &rot,int x){
		int a,b,c,d;
		split_by_rank(rot,x-1,a,b);
		split_by_rank(b,1,c,d);
		T e=val[c];
		rot=merge(a,merge(c,d));
		return e;
	}


	T bef(int x){
		int a,b,d,e;
		split_by_val(root,x-1,a,b);
		T c=findK(a,sz[a]);
		root=merge(a,b);
		return c;
	}

	T aft(int x){
		int a,b;
		split_by_val(root,x,a,b);
		T c=findK(b,1);
		root=merge(a,b);
		return c;
	}
};

Treap<int> T;
const int N=2e5+5;

int main(){
	n=read();while(n--){
		int opt=read();int x=read();
		switch(opt){
			case 1:T.insert(x);break;
			case 2:T.remove(x);break;
			case 3: printf("%d\n",T.findRank(x));break;
			case 4: printf("%d\n",T.findK(T.root,x));break;
			case 5: printf("%d\n",T.bef(x));break;
			case 6: printf("%d\n",T.aft(x));break;
		}
	}return 0;
}

代码version2


//2020.9.5
//loj104 普通平衡树
//fhq treap
//
#include <bits/stdc++.h>
using namespace std;
#define inc(i,a,b) for(int i=a;i<=b;i++)
#define dec(i,a,b) for(int i=a;i>=b;i--)
#define ll long long 
#define mst(a,b) memset(a,b,sizeof a)
#define pb push_back
inline int read(){
    char ch=getchar();int f=1,x=0;
	while(!isdigit(ch)) { if(ch=='-') f=-1;ch=getchar();}
	while(isdigit(ch)){ x=x*10+ch-'0';ch=getchar();}
	return f*x;
}


const int N=1e5+10;
int n;
struct Tree{
	int val,key,siz; //权值,随机权重，子树大小
	int son[2];		// 左右儿子　0左1右
	//清空该节点，用于删除
	void res(){ son[0]=son[1]=val=key=siz=0; }
}tree[N];
int ins;
int mem[N],inm; //内存回收池
int root;

void update(int o){
	tree[o].siz=tree[tree[o].son[0]].siz+tree[tree[o].son[1]].siz+1;
}





// x,y 两个子树，的且所有的节点的值都小于ｙ的所有节点的值，

// 随机权重都以小根堆的形式存储
int merge(int x,int y){
	if(!x||!y) return x+y; //若有一棵树为0则说明该树为空或已合并完成
	// 若x的随机值小于y的
	// x的右子树和y合并，返回的根作为x的右子树
	if(tree[x].key<tree[y].key){
		tree[x].son[1]=merge(tree[x].son[1],y);

		update(x);
		return x;
	}else {
		//否则y的左子树和x合并，返回的根作为y的左子树
		tree[y].son[0]=merge(x,tree[y].son[0]);
		update(y);
		return y;
	}
}

//split 有两种写法
//按照权值拆或按照排名拆分
//设定一个基准a,小于等于a的节点全部进入左树,大于a的节点全部进入右树

//按照权值拆分为两棵子树(注意要写引用）
void split1(int now,int k,int &x,int &y){
	if(!now) { x=y=0;return ;}
	if(tree[now].val<=k){
		x=now;
		split1(tree[now].son[1],k,tree[now].son[1],y);
	}else {
		y=now;
		split1(tree[now].son[0],k,x,tree[now].son[0]);
	}
	update(now);
}

//按照排名split
void split2(int now,int k,int &x,int &y){
	if(!now) { x=y=0;return;} //子树为0,说明无需拆分或者拆分完毕,返回
//	update(now);
	if(k>tree[tree[now].son[0]].siz){ // 若子树+1<=k
		x=now;
		split2(tree[now].son[1],k-tree[tree[now].son[0]].siz-1,tree[now].son[1],y);
	}else {
		y=now;
		split2(tree[now].son[0],k,x,tree[now].son[0]);
	}
	update(now);
}

void insert(int x){
	//新建节点
	int u=(inm?mem[inm--]:++ins);
	tree[u].key=rand();
	tree[u].val=x;
	tree[u].siz=1;
	int a,b;
	split1(root,x,a,b);
	root=merge(merge(a,u),b);
}



void delet(int x){
	int a,b,c,d,e,f;
	split1(root,x,a,b);
	split1(a,x-1,c,d);

	split2(d,1,e,f);
	mem[++inm]=e;
	tree[e].res();
	root=merge(merge(c,f),b);
}

int findrnk(int x){
	int a,b,c;
	split1(root,x-1,a,b);
	c=tree[a].siz+1;
	root=merge(a,b);
	return c;
}


//查询第ｘ小值
int finnum(int &rot,int x){
	int a,b,c,d,e;
	split2(rot,x-1,a,b);
	split2(b,1,c,d);
	e=tree[c].val;
	rot=merge(a,merge(c,d));
	return e;
}

//查询x的前驱
int las(int x){
	int a,b,c;
	split1(root,x-1,a,b);
	c=finnum(a,tree[a].siz);
	root=merge(a,b);
	return c;
}

//查询x的后继
int nex(int x){
	int a,b,c;
	split1(root,x,a,b);
	c=finnum(b,1);
	root=merge(a,b);
	return c;
}

int main(){
	n=read();while(n--){
		int opt=read();int x=read();
		switch(opt){
			case 1: insert(x);break;
			case 2: delet(x);break;
			case 3: printf("%d\n",findrnk(x));break;
			case 4: printf("%d\n",finnum(root,x));break;
			case 5: printf("%d\n",las(x));break;
			case 6: printf("%d\n",nex(x));break;
		}
	}return 0;
}

文艺平衡树　

解决的是区间问题，感觉和lazy标记的线段树很像．

参考的资料：　https://www.cnblogs.com/mjtcn/p/8029680.html

是splay 的模板题，有时间学一下．

题目链接

// ac
// 105 普通平衡树
#include <bits/stdc++.h>
using namespace std;
#define inc(i,a,b) for(int i=a;i<=b;i++)
#define dec(i,a,b) for(int i=a;i>=b;i--)
#define ll long long 
#define mst(a,b) memset(a,b,sizeof a)
#define pb push_back
inline int read(){
	char ch=getchar();int f=1,x=0;
	while(!isdigit(ch)) { if(ch=='-') f=-1;ch=getchar();}
	while(isdigit(ch)){ x=x*10+ch-'0';ch=getchar();}
	return f*x;
}


//by Sshwy
namespace RA{
	int rnd(int p){return 1ll*rand()*rand()%p;}
	int rnd(int L,int R){return rnd(R-L+1)+L;}
}

const int SZ = 1e5+10;
// fhq treap 的模板
template<class T>
struct Treap{
	int root,tot;
	int mem[SZ],memp;
	int lc[SZ],rc[SZ],sz[SZ],tag[SZ];
	unsigned int rnd[SZ];

	T val[SZ];

	void clear(){
		fill(lc,lc+tot+1,0);
		fill(rc,rc+tot+1,0);
		fill(sz,sz+tot+1,0);
		root=tot=0;
	}

	Treap(){
		root=tot=0;
		srand(clock()+time(0));
		val[0] = 0;
	}

	inline void pushup(int u){
		sz[u] = sz[lc[u]]+sz[rc[u]]+1;
	}

	inline void pushdown(int o){
		if(tag[o]){
			tag[lc[o]]^=1;
			tag[rc[o]]^=1;
			swap(lc[o],rc[o]);
			tag[o]^=1;
		}
	}
	inline int newnode(int x){
		int u=memp?mem[memp--]:++tot;
		val[u]=x, sz[u]=1, rnd[u]=rand();
		return u;
	}

	//x,y两个子树,且所有的节点的值都小于y的所有节点的值
	//随机权重以小根堆的形式存储
	int merge(int x,int y){//x<y
		if(!x||!y)return x+y;
		pushdown(x);
		pushdown(y);
		//if(rand()%(sz[x]+sz[y])<sz[x])return rc[x]=merge(rc[x],y), pushup(x), x;
		if(rnd[x]<rnd[y])return rc[x]=merge(rc[x],y), pushup(x), x;
		else return lc[y]=merge(x,lc[y]), pushup(y), y;
	}

	void split(int u,const int left_size,int &x,int &y){
		if(!u)return x=y=0,void();
		pushdown(u);
		if(sz[lc[u]]+1<=left_size)x=u,split(rc[u],left_size-sz[lc[u]]-1,rc[u],y);
		else y=u,split(lc[u],left_size,x,lc[u]);
		pushup(u);
	}

	//按住权值拆分为两颗子树
	void split_by_val(int now,const T k,int &x,int &y){
		if(!now) return x=y=0,void();
		pushdown(now);
		if(val[now]<=k) x=now,split_by_val(rc[now],k,rc[now],y);
		else y=now,split_by_val(lc[now],k,x,lc[now]);
		pushup(now);
	}

	//按照排名拆分成两颗子树
	void split_by_rank(int now,int k,int &x,int &y){
		if(!now) return x=y=0,void();
		pushdown(now);
		if(sz[lc[now]]+1<=k) x=now,split_by_rank(rc[now],k-sz[lc[now]]-1,rc[now],y);
		else y=now,split_by_rank(lc[now],k,x,lc[now]);
		pushup(now);
	}

	void insert(T v){
		int a,b,u=memp?mem[memp--]:++tot;
		val[u]=v;
		sz[u]=1;
		rnd[u]=rand();
		split_by_val(root,v,a,b);
		root=merge(merge(a,u),b);
	}

	inline void reverse(int l,int r){
		int a,b,c,d;
		split_by_rank(root,r,a,b);
		split_by_rank(a,l-1,c,d);
		tag[d]^=1;
		root=merge(merge(c,d),b);
	}

	
	void print(int o){
		if(!o) return;
		pushdown(o);
		print(lc[o]);
		printf("%d ",val[o]);
		print(rc[o]);
	}
};

Treap<int> T;
const int N=1e5+10;
int n,m;


int main(){
	n=read();m=read();inc(i,1,n) T.insert(i);
	while(m--){ int a=read(),b=read();T.reverse(a,b);}
	T.print(T.root);putchar('\n');
	return 0;
}

模板留存 fhq treap

本博客所有文章除特别声明外，均采用 CC BY-SA 4.0 协议，转载请注明出处！

利用fhqTreap解决区间序列问题上一篇

初探treap1 下一篇