fhq-treap初学
codesonic
2018-07-13 21:50:50
原来你就是无旋treap???
fhq-treap的思想就是函数式编程，即通过简单函数的组合实现操作，这在fhq-treap中有很大体现
fhq-treap用两个函数merge和split实现了平衡树的主要操作
先来瞻仰一下这两个函数：
merge:
```cpp
void merge(int &x,int l,int r){
if(!l||!r) x=l+r;
else if(rnd[l]<rnd[r]) x=l,merge(rs[x],rs[x],r),up(x);
else x=r,merge(ls[x],l,ls[x]),up(x);
}
```
merge把l和r两棵树合并成了x，代码很显然就不多说了~~（其实是因为我讲不通）~~
split:
```cpp
void split(int x,int &l,int &r,int k){
if(!k) l=0,r=x;
else if(k==size[x]) l=x,r=0;
else if(k<=size[ls[x]]) r=x,split(ls[x],l,ls[x],k),up(x);
else l=x,split(rs[x],rs[x],r,k-size[ls[x]]-1),up(x);
}
```
split把x树分成了l和r两棵树
接下来是主要部分，也是fhq-treap用merge和split实现许多操作的思想体现
insert插入元素:
```cpp
inline void insert(int delta){
int x,y,rk=rank(root,delta);
split(root,x,y,rk);
build(tmp,delta);
merge(x,x,tmp);
merge(root,x,y);
}
```
insert函数里，先把整棵treap按要插入的值拆成了两棵，再把要加的节点和其中一半合并，最后两半一起合并重新变成完整的treap
del删除元素
```cpp
inline void del(int delta){
int x,y,z,rk=rank(root,delta)+1;
split(root,x,y,rk);
split(x,x,z,rk-1);
merge(root,x,y);
}
```
同理，把treap先拆成两半，然后把其中一半中的要删除的节点拆出来，再把那大的两半合起来，完毕
其他的操作也差不多啦
code for [P3369 【模板】普通平衡树](https://www.luogu.org/problemnew/show/P3369)
```cpp
#include<cstdio>
#include<algorithm>
using namespace std;
const int maxn=500010;
int n,m,x,y,z,tot,opt;
struct fhq_treap{
int rnd[maxn],sum[maxn],size[maxn],ls[maxn],rs[maxn],root,tmp;
inline void build(int &x,int delta){
rnd[x=++tot]=rand()<<15|rand();
sum[x]=delta;
size[x]=1;
}
inline void up(int x){
if(!x) return ;
size[x]=size[ls[x]]+size[rs[x]]+1;
}
void merge(int &x,int l,int r){
if(!l||!r) x=l+r;
else if(rnd[l]<rnd[r]) x=l,merge(rs[x],rs[x],r),up(x);
else x=r,merge(ls[x],l,ls[x]),up(x);
}
void split(int x,int &l,int &r,int k){
if(!k) l=0,r=x;
else if(k==size[x]) l=x,r=0;
else if(k<=size[ls[x]]) r=x,split(ls[x],l,ls[x],k),up(x);
else l=x,split(rs[x],rs[x],r,k-size[ls[x]]-1),up(x);
}
int rank(int x,int w){
if(!x) return 0;
if(sum[x]>=w) return rank(ls[x],w);
return rank(rs[x],w)+size[ls[x]]+1;
}
inline void insert(int delta){
int x,y,rk=rank(root,delta);
split(root,x,y,rk);
build(tmp,delta);
merge(x,x,tmp);
merge(root,x,y);
}
inline void del(int delta){
int x,y,z,rk=rank(root,delta)+1;
split(root,x,y,rk);
split(x,x,z,rk-1);
merge(root,x,y);
}
inline int find(int delta)
{
int x,y,z,ans;
split(root,x,y,delta);
split(x,z,x,delta-1);
ans=sum[x];
merge(x,z,x);
merge(root,x,y);
return ans;
}
inline int pre(int delta){
int x,y,z,ans,rk=rank(root,delta);
split(root,x,y,rk);
split(x,z,x,rk-1);
ans=sum[x];
merge(x,z,x);
merge(root,x,y);
return ans;
}
inline int sub(int delta){
int x,y,z,ans,rk=rank(root,delta+1);
split(root,x,y,rk+1);
split(x,z,x,rk);
ans=sum[x];
merge(x,z,x);
merge(root,x,y);
return ans;
}
}T;
int main()
{
srand(2009);
scanf("%d",&n);
T.rnd[0]=T.sum[0]=(1<<30);
while(n--){
int opt;
scanf("%d%d",&opt,&x);
if(opt==1) T.insert(x);
else if(opt==2) T.del(x);
else if(opt==3)printf("%d\n",T.rank(T.root,x)+1);
else if(opt==4)printf("%d\n",T.find(x));
else if(opt==5)printf("%d\n",T.pre(x));
else printf("%d\n", T.sub(x));
}
}
```
文艺平衡树也是乱搞，对于要翻转的区间，交换左子树右子树，然后打标记即可
```cpp
// luogu-judger-enable-o2
// luogu-judger-enable-o2
// luogu-judger-enable-o2
#include<cstdio>
#include<algorithm>
using namespace std;
const int maxn=500010;
int n,m,x,y,z,tot,opt;
inline void read(int &x){
x=0;int f=1;char c=getchar();
while(c<'0'||c>'9'){if(c=='-')f=-f;c=getchar();}
while(c>='0'&&c<='9'){x=x*10+c-'0';c=getchar();}
x*=f;
}
struct fhq_treap{
int rnd[maxn],sum[maxn],size[maxn],ls[maxn],rs[maxn],root,tmp;
bool rev[maxn];
inline void change(int x){
rev[x]^=1;
swap(ls[x],rs[x]);
}
inline void down(int x)
{
if(!x) return;
if(rev[x]) change(ls[x]),change(rs[x]);
rev[x]=0;
}
inline void build(int &x,int delta){
rnd[x=++tot]=rand()<<15|rand();
sum[x]=delta;
size[x]=1;
}
inline void up(int x){
if(!x) return ;
size[x]=size[ls[x]]+size[rs[x]]+1;
}
void merge(int &x,int l,int r){
if(!l||!r) x=l+r;
else if(rnd[l]<rnd[r]) down(x=l),merge(rs[x],rs[x],r),up(x);
else down(x=r),merge(ls[x],l,ls[x]),up(x);
}
void split(int x,int &l,int &r,int k){
if(!k) l=0,r=x;
else if(k==size[x]) l=x,r=0;
else if(k<=size[ls[x]]) down(r=x),split(ls[x],l,ls[x],k),up(x);
else down(l=x),split(rs[x],rs[x],r,k-size[ls[x]]-1),up(x);
}
inline void insert(int pos,int delta)
{
int x,y;
split(root,x,y,pos);
merge(x,x,delta);
merge(root,x,y);
}
inline void del(int pos,int delta){
int x,y,z;
split(root,x,y,pos);
split(x,x,z,pos-1);
merge(root,x,y);
}
inline void reverse(int l, int r)
{
int x,y,z;
split(root,x,y,r);
split(x,z,x,l-1);
change(x);
merge(x,z,x);
merge(root,x,y);
}
void getans(int num){
int x,y,z;
split(root,x,y,num);
split(x,z,x,num-1);
printf("%d ",sum[x]);
merge(x,z,x);
merge(root,x,y);
}
}T;
int main()
{
srand(2009);
read(n);
read(m);
T.rnd[0]=T.sum[0]=(1<<30);
for(int i=1;i<=n;i++){
int tmp;
T.build(tmp,i);
T.merge(T.root,T.root,tmp);
}
while(m--){
read(x);
read(y);
T.reverse(x,y);
}
for(int i=1;i<=n;i++){
T.getans(i);
}
return 0;
}
```
又比splay短又比splay快的数据结构
似乎要全方位吊打splay了