当前位置：首页 > news >正文

FHQ-Treap

news 2025/9/18 2:48:12

的确算是比较好调好写的平衡树了（我也只会这一个平衡树了 QwQ）。

FHQtreap是哈？

FHQ-Treap在没有旋转的情况下通过分裂合并实现了Tree值满足BST性质（实际是数之间的相对位置确定，如区间反转等可能导致Tree值并不满足BST，此时实际维护的是区间数相对位置），Rand值满足堆性质。

建点

直接上代码。

ll bd(ll x){t[++tot]={0,0,x,rnd(),1};return tot;
}

对于某些题空间不足，可将删除的点放入栈中，在bd时优先调用。

上传

看要传什么，最普通的情况下多半只传size。

void pu(ll x){t[x].sz=t[t[x].lc].sz+t[t[x].rc].sz+1;
}

分裂split

分为权值分裂和排名（sz（我认为，多半是））分裂。

权值分裂

若要将此树分为权值小于等于 \(x\) 的树和大于 \(x\) 的树，可将根节点权值与 \(x\) 比较，若根节点小于等于 \(x\)，说明左子树和根节点都小于等于 \(x\)，那么只需要把右子树中大于 \(x\) 的部分分出去，成为另一颗树即可。

若根节点大于 \(x\)，说明右子树和根节点都大于 \(x\)，那么只需要把左子树中小于等于 \(x\) 的部分分出去，成为另一颗树即可。

具体实现使用递归。

void split(ll u,ll &x,ll &y,ll val){if(!u){x=0,y=0;return;}if(t[u].sum<=val)x=u,split(t[u].rc,t[u].rc,y,val);elsey=u,split(t[u].lc,x,t[u].lc,val);pu(u);
}

排名分裂

若要将此树分为大小小于等于 \(x\) 的树和剩下的树，可将左子树大小与 \(x\) 比较，若左子树小于 \(x\)，说明左子树加根节点大小小于等于 \(x\)，那么只需要把右子树中大小小于等于 \(x- l.sz -1\) 的部分分出来补给左子树即可

若左子树大于等于 \(x\)，说明大小小于等于 \(x\) 的树一定可在左子树中分出，将左子树继续分裂即可。

具体实现使用递归。

void split_sz(ll u,ll &x,ll &y,ll val){if(!u){x=0,y=0;return;}if(t[t[u].lc].sz<val)x=u,split(t[u].rc,t[u].rc,y,val-t[t[u].lc].sz-1);elsey=u,split(t[u].lc,x,t[u].lc,val);pu(u);
}

合并

若要将 \(u,v\) 两棵树合并，必须保证 \(u\) 中所有节点的权值小于等于 \(v\) 中的节点权值，才能使得合并后的树权值仍旧满足BST性质（倘若你没有BST的要求，就不需要满足此性质）。合并后的树实际是保证 \(u\) 的节点一定在 \(v\) 左边（对于 \(u\) 节点来说）。

因为我们需要保证节点 \(Rand\) 值满足堆性质，所以需要比较两颗子树根的 \(Rand\) 值，从而确定究竟是将 \(v\) 与 \(u\) 的右子树揉在一起还是将 \(u\) 与 \(v\) 的左子树揉在一起。

ll merge(ll x,ll y){if(!x||!y)return x+y;if(t[x].rnd>t[y].rnd){t[x].rc=merge(t[x].rc,y);pu(x);return x;}else{t[y].lc=merge(x,t[y].lc);//传参顺序千万不要反。pu(y);return y;}
}

插入权值为 \(x\) 的点

void insert(ll x){ll l,r;split(rt,l,r,x);rt=merge(merge(l,bd(x)),r);
}

删除一个权值为 \(x\) 的点

void del(ll x){ll l,r,l1;split(rt,l,r,x);split(l,l1,l,x-1);l=merge(t[l].lc,t[l].rc);rt=merge(merge(l1,l),r);
}

求权值为 \(x\) 的点在树上的排名（不算与其相等的数）

ll myrank(ll x){ll l,r,sum;split(rt,l,r,x-1);sum=t[l].sz+1;rt=merge(l,r);return sum;
}

求 \(u\) 树上排名为 \(x\) 点的编号与权值

ll Rank(ll u,ll x){if(x==t[t[u].lc].sz+1)return u;if(x<=t[t[u].lc].sz)return Rank(t[u].lc,x);return Rank(t[u].rc,x-t[t[u].lc].sz-1);
}

ll kth(ll u,ll k){return t[Rank(u,k)].sum;
}

求前驱

ll qq(ll x){ll l,r,sum;split(rt,l,r,x-1);sum=kth(l,t[l].sz);rt=merge(l,r);return sum;
}

求后继

ll hj(ll x){ll l,r,sum;split(rt,l,r,x);sum=kth(r,1);rt=merge(l,r);return sum;
}

在来个纯享版

// Problem: P3369 【模板】普通平衡树
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/P3369
// Memory Limit: 128 MB
// Time Limit: 1000 ms
// 
// Powered by CP Editor (https://cpeditor.org)#include<bits/stdc++.h>
#include<queue>
#define endl "\n"
#define ll long long
#define ft first
#define sd second
// #define int long long
#define db long double
#define pb push_back
#define mp make_pair
#define pe(j) (1ll<<(j))
#define foe(n) for(int i=1;i<=n;i++)
using namespace std;
inline void write(ll x);
inline ll read();
const ll N=1e6+5,INF=0x3f3f3f3f3f3f3f3f,mod=998244353;
ll n,T,ans,m,k;
struct PHS{ll lc,rc,sum,rnd,sz;
}t[N];
mt19937 rnd(time(0));void pu(ll x){t[x].sz=t[t[x].lc].sz+t[t[x].rc].sz+1;
}
void split(ll u,ll &x,ll &y,ll val){if(!u){x=0,y=0;return;}if(t[u].sum<=val)x=u,split(t[u].rc,t[u].rc,y,val);elsey=u,split(t[u].lc,x,t[u].lc,val);pu(u);
}
void split_sz(ll u,ll &x,ll &y,ll val){if(!u){x=0,y=0;return;}if(t[t[u].lc].sz<val)x=u,split(t[u].rc,t[u].rc,y,val-t[t[u].lc].sz-1);elsey=u,split(t[u].lc,x,t[u].lc,val);pu(u);
}
ll merge(ll x,ll y){if(!x||!y)return x+y;if(t[x].rnd>t[y].rnd){t[x].rc=merge(t[x].rc,y);pu(x);return x;}else{t[y].lc=merge(x,t[y].lc);pu(y);return y;}
}
ll tot,rt;
ll bd(ll x){ t[++tot]={0,0,x,rnd(),1}; return tot;}void insert(ll x){ll l,r;split(rt,l,r,x);rt=merge(merge(l,bd(x)),r);
}
void del(ll x){ll l,r,l1;split(rt,l,r,x);split(l,l1,l,x-1);l=merge(t[l].lc,t[l].rc);rt=merge(merge(l1,l),r);
}
ll xyx(ll x){ll l,r,sum;split(rt,l,r,x-1);sum=t[l].sz+1;rt=merge(l,r);return sum;
}
ll Rank(ll u,ll x){if(x==t[t[u].lc].sz+1)return u;if(x<=t[t[u].lc].sz)return Rank(t[u].lc,x);return Rank(t[u].rc,x-t[t[u].lc].sz-1);
}
ll kth(ll u,ll k){return t[Rank(u,k)].sum;}
ll qq(ll x){ll l,r,sum;split(rt,l,r,x-1);sum=kth(l,t[l].sz);rt=merge(l,r);return sum;
}
ll hj(ll x){ll l,r,sum;split(rt,l,r,x);sum=kth(r,1);rt=merge(l,r);return sum;
}
signed main(){cin.tie(0);cout.tie(0);ios::sync_with_stdio(false);cin>>n;while(n--){ll op,x;cin>>op>>x;if(op==1){insert(x);}if(op==2){del(x);}if(op==3){cout<<xyx(x)<<endl;}if(op==4){cout<<kth(rt,x)<<endl;}if(op==5){cout<<qq(x)<<endl;}if(op==6){cout<<hj(x)<<endl;}}return 0;
}//------------------------------------------------------------------------------------------
//read&write
inline ll read(){ll x=0,w=1;char ch=0;while(ch<'0'||ch>'9'){if(ch=='-')w=-1;ch=getchar();}while(ch>='0'&&ch<='9'){x=(x<<3)+(x<<1)+(ch-'0');ch=getchar();}return x*w;
}
inline void write(ll x){static ll sta[35];ll top=0;do{sta[top++] = x % 10, x /= 10;}while (x);while(top) putchar(sta[--top]+48);
}