2021.12.08 平衡树——FHQ Treap

http://www.yhzq-blog.cc/fhqtreapzongjie/

https://www.cnblogs.com/zwfymqz/p/7151959.html

1. FHQ Treap

FHQ Treap与Treap一样，都有关键码和优先级。关键码满足二叉搜索树的性质——左子树的关键码小于根节点，右子树的关键码大于根节点。优先级满足堆的性质——所有子树的优先级均大于或小于根节点的优先级的值。

因此，本篇博客默认优先级越大越优。

2. 建新点add

val[cnt] ：cnt节点的关键码的值

key[cnt] ：cnt节点的优先级的值

cnt ：记录点的个数

代码如下：

inline int add(int x){

	sizei[++cnt]=1;

	val[cnt]=x;

	key[cnt]=rand();

	return cnt;

}

3. 分裂split

作为无旋Treap，FHQ Treap的一切操作都是建立在分裂与合并上的。

分裂有两种情况，第一种按照关键码大小分裂，第二种按照子树大小分裂。

3.1 按照关键码大小分裂

rt ：目前所在的节点

son[x][0/1] ：0 \(\rightarrow\) 左子树，1 \(\rightarrow\) 右子树

x ：分裂后分成两棵树的左边的树

y ：分裂后分成两棵的树右边的树

vali ：分裂的标准，小于等于就分到左边，大于等于就分到右边

如果 \(val[rt]<=vali\) ，左子树分到x，继续分裂右子树；

如果 \(val[rt]>vali\) ，右子树分到y，继续分裂左子树。

分裂前记得pushdown一下，分裂后记得update。

代码如下：

inline void split(int rt,int vali,int &x,int &y){

	if(!rt)return (void)(x=y=0);

	pushdown(rt);

	if(val[son[rt][0]]>vali)

	y=rt,split(son[rt][0],vali,x,son[rt][0]);

	else x=rt,split(son[rt][1],vali,son[rt][1],y);

	update(rt);

}

update的代码：

inline void update(int x){

	sizei[x]=sizei[son[x][0]]+sizei[son[x][1]]+1;

}

pushwon的代码：

inline void pushdown(int x){

	if(!lazy[x]||!x)return ;

	swap(son[x][0],son[x][1]);

	if(son[x][0])lazy[son[x][0]]^=1;

	if(son[x][1])lazy[son[x][1]]^=1;

	lazy[x]=0;

}

3.2 按照子树大小分裂

k ：以k为分界线，前k-1个节点分到一棵树中，k以及k之后的节点分到另一颗树中。

类似于Treap根据排名找分数。

代码如下：

inline void split(int rt,int k,int &x,int &y){

	if(!rt)return (void)(x=y=0);

	pushdown(rt);

	if(sizei[son[rt][0]]>=k)

	y=rt,split(son[rt][0],k,x,son[rt][0]);

	else x=rt,split(son[rt][1],k-sizei[son[rt][0]]-1,son[rt][1],y);

	update(rt);

}

3.3 分裂后x子树与y子树的解释

int &x; ：是按地址出送，只要修改 x就是把x所在地址的x直接修改了

所以在 if(sizei[son[rt][0]]>=k)y=rt,split(son[rt][0],k,x,son[rt][0]); 中，修改了y的值，把y的值变为肯定不会变的rt。我们要继续分裂的是子树 son[x][0] ，所以 son[x][0] 中子树大小小于k的全部分到x中，剩下的继续留在 son[x][0] 中， sizei[son[rt][0]]<k 时同理。直到把整棵树都分裂完为止，返回上一级。到x时，这个时候x的左右儿子被更新过了，按照子树大小的标准分裂。对于根节点来说，它的子树被完整地分成两份存在x和y中（也可能是其他的变量/笑哭）.

4. 合并merge

注：合并返回的是结点的编号

x ：被合并的左子树

y ：被合并的右子树

如果两棵子树中任意一棵子树为空子树，直接返回 x+y ，反正是返回编号；

如果x优先级高于y优先级，把 son[x][1] 与 y 合并；

否则把 x 与 son[y][0] 合并。

代码如下：

inline int merge(int x,int y){

	if(!x||!y)return x+y;

	pushdown(x);pushdown(y);

	if(key[x]<key[y]){

		son[y][0]=merge(x,son[y][0]);

		update(y);

		return y;

	}else{

		son[x][1]=merge(son[x][1],y);

		update(x);

		return x;

	}

}

记得pushdown与update~

5. 区间翻转rotate

lazy[x] ：类似于线段树的懒标记，功能也一样

L ：区间左端点

R ：区间右端点

注：以k为标准就是把 \(1,2,\cdots,k-1\) 分到一棵子树，把 \(k,k+1,\cdots,n\) 分到另一棵子树。

先把以 root 为根节点的子树以R+1为标准分成两棵——左子树为 u ，右子树为 v ；

再把以 u 为根节点的子树以L为标准分成两棵——左子树为 w ，右子树为 x 。

x 包含区间L到R，更新 lazy[x] ，合并。

合并一定要按顺序，先合并 w 与 x ，再把新结果一起合并 v 。

代码如下：

inline void rotate(int L,int R){

	int u,v,w,x;

	split(root,R+1,u,v);

	split(u,L,w,x);

	lazy[x]^=1;

	root=merge(merge(w,x),v);

}

6. 建树build

和线段树差不多，只不过是一边建新点一边建子树，不过 FHQ Treap左子树不包含本节点。

代码如下：

inline int build(int l,int r){

	if(l>r)return 0;

	int mid=(l+r)>>1;

	int x=add(mid-1);

	son[x][0]=build(l,mid-1);

	son[x][1]=build(mid+1,r);

	update(x);

	return x;

}

7. 模板题 P3391 【模板】文艺平衡树

https://www.luogu.com.cn/problem/P3391

代码如下：

#include<cstdio>

#include<iostream>

#include<algorithm>

#include<cstring>

#include<stack>

#define IOS ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);

using namespace std;

const int N=1e5+10;

int n,m,a[N];

int root,cnt,son[N][2],val[N],sizei[N],lazy[N],key[N];

inline int read(){

	int s=0,w=1;

	char ch=getchar();

	while(ch<'0'||ch>'9'){

		if(ch=='-')w=-1;

		ch=getchar();

	}

	while(ch<='9'&&ch>='0'){

		s=s*10+ch-'0';

		ch=getchar();

	}

	return s*w;

}

inline void update(int x){

	sizei[x]=sizei[son[x][0]]+sizei[son[x][1]]+1;

}

inline void pushdown(int x){

	if(!lazy[x]||!x)return ;

	swap(son[x][0],son[x][1]);

	if(son[x][0])lazy[son[x][0]]^=1;

	if(son[x][1])lazy[son[x][1]]^=1;

	lazy[x]=0;

}

inline int add(int x){

	sizei[++cnt]=1;

	val[cnt]=x;

	key[cnt]=rand();

	return cnt;

}

inline void split(int rt,int k,int &x,int &y){

	if(!rt)return (void)(x=y=0);

	pushdown(rt);

	if(sizei[son[rt][0]]>=k)

	y=rt,split(son[rt][0],k,x,son[rt][0]);

	else x=rt,split(son[rt][1],k-sizei[son[rt][0]]-1,son[rt][1],y);

	update(rt);

}

inline int merge(int x,int y){

	if(!x||!y)return x+y;

	pushdown(x);pushdown(y);

	if(key[x]>=key[y]){

		son[y][0]=merge(x,son[y][0]);

		update(y);

		return y;

	}else{

		son[x][1]=merge(son[x][1],y);

		update(x);

		return x;

	}

}

inline void rotate(int L,int R){

	int u,v,w,x;

	split(root,R+1,u,v);

	split(u,L,w,x);

	lazy[x]^=1;

	root=merge(merge(w,x),v);

}

inline int build(int l,int r){

	if(l>r)return 0;

	int mid=(l+r)>>1;

	int x=add(mid-1);

	son[x][0]=build(l,mid-1);

	son[x][1]=build(mid+1,r);

	update(x);

	return x;

}

inline void dfs(int x){

	if(!x)return ;

	pushdown(x);

	if(son[x][0])dfs(son[x][0]);

	if(val[x]>=1&&val[x]<=n)cout<<val[x]<<" ";

	if(son[x][1])dfs(son[x][1]);

}

int main(){

	n=read();m=read();

	root=build(1,n+2);

	//dfs(root);cout<<endl;

	for(int i=1;i<=m;i++){

		int u,v;

		u=read();v=read();

		rotate(u,v);

	}

	dfs(root);

	return 0;

}

2021.12.08 平衡树——FHQ Treap