FHQ Treap 学习笔记

ZHONGZIJIE0608 · 2024-04-19 21:47:47 · 个人记录

学了三年才学平衡树的屑。（doge）

平衡树。

一种二叉搜索树。

其实就是算排名这些在序列上难解决的问题放在树上解决。例如：树可以找子树。

平衡树（Treap）不是绝对平衡，而是用随机数构造一个堆来保证期望平衡。

通常，平衡树有两种建树方法：

• 用权值存储，用于算值域相关。

• 用下标存储，用于算下标相关。

感谢 FHQ。

FHQ Treap，是一个由巨佬 FHQ 命名的不用旋转的 Treap（一种平衡树）。

它最大的特点就是——不用旋转 所有操作基于分裂和合并两个操作。

为向我们这种搞不清旋转的蒟蒻创造了福音。

分裂。

分裂（split），就是把一棵平衡树用 val 劈成两半，左半边的树 A 小于等于 val，右半边的树 B 大于 val。

学这个的时候，脑子里的东西 be like:

开个玩笑。

道理很简单，我们要在树里面查一个节点的排名，就可以把树劈成两半算个数。

我们知道，平衡树中左子树中的点小于等于根，右子树中的点大于根。

那么，从根开始搜。如果子树根 K 小于等于 val，A 也就是 K 就先确定为左树根，然后从 K 的右子树和 B 中找 B 树的根。

反之，如果子树根 K 大于 val，B 也就是 K 就先确定为右树根，然后从 K 的左子树和 A 中找 A 树的根。

如果 K 不存在（为空），A=B=0。

这样会有一种情况：如果小于等于 val 的最大的点和左边的根不直接连通，不会劈成森林吗？

答案是不会。我们在更新左右子树时使用取地址符，在选完 A,B 后就会自动更新为子树（连边）。

最后记得更新 K 这个树的大小为左右子树大小 +1。

inline void upd(int k){tree[k].size=tree[tree[k].lc].size+tree[tree[k].rc].size+1;return;}
inline void split(int k,int &a,int &b,int val){
    if(!k){a=b=0;return;}
    if(tree[k].val<=val)a=k,split(tree[k].rc,tree[k].rc,b,val);
    else b=k,split(tree[k].lc,a,tree[k].lc,val);
    upd(k);return;
}

合并。

把树劈开拿信息之后，总是要把树并起来的。

设我们有两棵树 A 和 B，合并成树 K。

钦定 B 的所有点权值大于 A。

先对于每一个点搞一个随机值。（随机完 A<B 概率为 \frac{1}{2}，有最小深度）

如果 A 的随机值小于 B 的随机值，把 B 放在 A 的右子树。当然，B 要与 A 原有的右子树竞争成下一个右子树。

如果 A 的随机值大于 B 的随机值，把 A 放在 B 的左子树。当然，A 要与 B 原有的左子树竞争成下一个左子树。

放在上面的树根就是合并后的根 K。

特别地，如果 A,B 中有一个为空，K=A+B。

更新 K 的大小。

inline void merge(int &k,int a,int b){
    if(!a||!b){k=a+b;return;}
    if(tree[a].rnk<tree[b].rnk)k=a,merge(tree[k].rc,tree[k].rc,b);
    else k=b,merge(tree[k].lc,a,tree[k].lc);
    upd(k);return;
}

其他操作。

有了分裂和合并这两个操作，剩下的操作就很好想了。

以 P3369 【模板】普通平衡树 举例。

插入一个点。

插入一个权值为 val 的点。

先初始化点 cur：权值为 val，大小为 1，左右子树为 0，随机值。

把树 K 按 val-1 劈成 A,B，将 A,cur 合并为 A，再合并 A,B 为 K。

inline int add_node(int val){tree[++tot]={val,rand(),0,0,1};return tot;}
inline void insert(int &k,int val){
    int a=0,b=0,cur=add_node(val);
    split(k,a,b,val-1);merge(a,a,cur);merge(k,a,b);return;
}

删除一个点。

删除一个权值为 val 的点。

注意：在 FHQ Treap 中，可能有多个权值相同的点。

把树 K 按 val 劈成 A,B，再把树 A 按 val-1 劈成 A,Z。这样树 Z 只有所有权值为 val 的点。

把 Z 的左右子树合并至 Z，就可以删除根节点。

接着合并 A,B,Z，合并方法同上。

inline void del(int &k,int val){
    int a=0,b=0,z=0;
    split(k,a,b,val);split(a,a,z,val-1);merge(z,tree[z].lc,tree[z].rc);
    merge(a,a,z);merge(k,a,b);return;
}

查询排名。

查询 val 的排名。

把树 K 按 val-1 劈成 A,B，排名就是 A 的大小加 1。记得合并 A,B。

inline int find_rank(int &k,int val){
    int a=0,b=0;split(k,a,b,val-1);
    int tmp=tree[a].size+1;
    merge(k,a,b);
    return tmp;
}

依据排名查询数。

查询排名为 x 的数。

显然，若根排名为 x，答案为根的权值。

否则：

若左子树点个数比 x 多，直接搜左子树。

反之，让 x 减去左子树和根的大小，搜右子树。

inline int find_num(int k,int x){
    while(tree[tree[k].lc].size+1!=x){
        if(tree[tree[k].lc].size>=x)k=tree[k].lc;
        else{
            x-=tree[tree[k].lc].size+1;
            k=tree[k].rc;
        }
    }
    return tree[k].val;
}

查询前驱。

查询 val 的前驱。

把树 K 按 val-1 劈成 A,B，前驱就是 A 中排名为 A 的大小的数。记得合并 A,B。

inline int prev(int &k,int val){
    int a=0,b=0;split(k,a,b,val-1);
    int tmp=find_num(a,tree[a].size);merge(k,a,b);
    return tmp;
}

查询后继。

查询 val 的后继。

把树 K 按 val 劈成 A,B，前驱就是 B 中第一个数。记得合并 A,B。

inline int suf(int &k,int val){
    int a=0,b=0;split(k,a,b,val);
    int tmp=find_num(b,1);merge(k,a,b);
    return tmp;
}

完整代码

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=1e6+10;
struct node{int val,rnk,lc,rc,size;}tree[N];
int n,tot,rt=0;//根初始为 0
inline void upd(int k){tree[k].size=tree[tree[k].lc].size+tree[tree[k].rc].size+1;return;}
inline int add_node(int val){tree[++tot]={val,rand(),0,0,1};return tot;}
inline void split(int k,int &a,int &b,int val){
    if(!k){a=b=0;return;}
    if(tree[k].val<=val)a=k,split(tree[k].rc,tree[k].rc,b,val);
    else b=k,split(tree[k].lc,a,tree[k].lc,val);
    upd(k);return;
}
inline void merge(int &k,int a,int b){
    if(!a||!b){k=a+b;return;}
    if(tree[a].rnk<tree[b].rnk)k=a,merge(tree[k].rc,tree[k].rc,b);
    else k=b,merge(tree[k].lc,a,tree[k].lc);
    upd(k);return;
}
inline void insert(int &k,int val){
    int a=0,b=0,cur=add_node(val);
    split(k,a,b,val-1);merge(a,a,cur);merge(k,a,b);return;
}
inline void del(int &k,int val){
    int a=0,b=0,z=0;
    split(k,a,b,val);split(a,a,z,val-1);merge(z,tree[z].lc,tree[z].rc);
    merge(a,a,z);merge(k,a,b);return;
}
inline int find_num(int k,int x){
    while(tree[tree[k].lc].size+1!=x){
        if(tree[tree[k].lc].size>=x)k=tree[k].lc;
        else{
            x-=tree[tree[k].lc].size+1;
            k=tree[k].rc;
        }
    }
    return tree[k].val;
}
inline int find_rank(int &k,int val){
    int a=0,b=0;split(k,a,b,val-1);
    int tmp=tree[a].size+1;
    merge(k,a,b);
    return tmp;
}
inline int prev(int &k,int val){
    int a=0,b=0;split(k,a,b,val-1);
    int tmp=find_num(a,tree[a].size);merge(k,a,b);
    return tmp;
}
inline int suf(int &k,int val){
    int a=0,b=0;split(k,a,b,val);
    int tmp=find_num(b,1);merge(k,a,b);
    return tmp;
}
signed main(){
    ios::sync_with_stdio(false);cin.tie(0),cout.tie(0);
    cin>>n;rt=0;
    srand(time(0));
    for(int i=1;i<=n;++i){
        int op,x;cin>>op;
        if(op==1)cin>>x,insert(rt,x);
        if(op==2)cin>>x,del(rt,x);
        if(op==3)cin>>x,cout<<find_rank(rt,x)<<'\n';
        if(op==4)cin>>x,cout<<find_num(rt,x)<<'\n';
        if(op==5)cin>>x,cout<<prev(rt,x)<<'\n';
        if(op==6)cin>>x,cout<<suf(rt,x)<<'\n';
    }
    return 0;
}

复杂度分析

平衡树是 \log n 层，复杂度就是 O(n \log n)。

例题

P2234 [HNOI2002] 营业额统计

上古省选黄题。STL大法好

依据题意，与这个点差距最小的点就是它的前驱和后继。套板子。

注意：不用找严格前驱和后继，所以在查前驱后继时查询子树应当包含 val 这个值。

Trick：有可能前驱后继找不到，插入两个哨兵节点（极大极小值）即可。

水平不够，菜就多练。

AC

P1486 [NOI2004] 郁闷的出纳员

古神题目。维护加点，全加，全减（伴随删点），依据排名查点，维护删了多少个点。

排名，考虑平衡树。由于平衡树里不好实现离散删点，我们引入一个偏移量 tag 统计工资的增减情况。

那么，就有离职条件：

x+tag<=min
=> x<=min-tag

直接删除一整个子树。

查第 K 大就是查 total-K+1 小。

平衡树维护。

AC

P2286 [HNOI2004] 宠物收养场

注意到，宠物店里不是人领养宠物（全是人）就是宠物看人（全是宠物）。

那么就只需要一个平衡树，按照题意跑前驱后继的运算就完啦~

AC

CF702F T-shirts

1. 按品质 q 从大到小，按照价格 c 从小到大排序；
2. 将 m 个人的钱作为权值建立一棵平衡树；
3. 枚举第 i 种衣服，价格为 c_i，将 c_i 将平衡树 split，则 a 树的人不买，b 树的人都买；
4. 维护两个懒标记，shirt 表示衣服数， money 表示扣除的钱数，则 b 树 shirt 标记 +1,money-c_i；
5. 标记下传就是给左右子节点打标记，时机有三个：split，merge，以及最后询问之前。
6. 将 b 树按 2c_i 进行 split，将较小权值的子树的节点依次插入 a 树，由于每次钱数减半，时间复杂度 O(N \log N \log V)

AC

#include<bits/stdc++.h>
using namespace std;
const int N = 3e6 + 5; //由于会重新插入，结点数是NlogN 
struct node 
{
    int val, ans, rnk, id, lc, rc, size, shirt, tag; //shirt和tag是标记 
}tree[N];
struct T_shirt
{
    int q, c;
}s[N]; 
int n, m, tot, root = 0, ans[N];

void update(int k) //更新以k为根节点的子树的size 
{
    tree[k].size = tree[tree[k].lc].size + tree[tree[k].rc].size + 1;
    return ;
}

int add_node(int val, int id, int ans) //新建一个结点 ,多带了2个参数，1个是原始下标，一个是购买的t shirt总数 
{
    tree[++tot].size = 1;
    tree[tot].id = id;
    tree[tot].val = val;
    tree[tot].ans = ans; //重新插入结点时，之前的答案不能重置 
    tree[tot].lc = tree[tot].rc = tree[tot].shirt = tree[tot].tag = 0;
    tree[tot].rnk = rand();
    return tot;
}
void addtag(int k, int shirt, int money)
{
    if(k == 0)
        return ;
    tree[k].val -= money; //当前节点剩余钱数 ，不是标记 
    tree[k].ans += shirt; //当前节点的衣服数 , 不是标记 
    ans[tree[k].id] = tree[k].ans; //维护原始下标对应的答案 
    tree[k].shirt += shirt; //衣服标记
    tree[k].tag += money; //钱数标记；
    return ; 
}
void pushdown(int k)
{
    if(tree[k].tag == 0 && tree[k].shirt == 0)  
        return ;
    addtag(tree[k].lc, tree[k].shirt, tree[k].tag);
    addtag(tree[k].rc, tree[k].shirt, tree[k].tag);
    tree[k].shirt = tree[k].tag = 0;
    return ;
} 
void split(int k, int &a, int &b, int val) //将k为根节点的子树分裂为a，b两颗树，且a树的值小于等于val，b反之 
{
    if(k == 0) //结点不存在 
    {
        a = b = 0; //左右子树也不存在 ,不能省，why？ 
        return ;
    }
    pushdown(k);
    if(tree[k].val <= val) //以k为根的子树 
    {
        a = k;
        split(tree[k].rc, tree[k].rc, b, val);
    } 
    else 
    {
        b = k;
        split(tree[k].lc, a, tree[k].lc, val);
    }
    update(k);
    return ;
}

void merge(int &k, int a, int b) // 合并a，b两颗树，其中a的权值全部 < b的权值
{
    if(a == 0 || b == 0) 
    {
        k = a + b;
        return ;
    }
    pushdown(k);
    if(tree[a].rnk < tree[b].rnk) //a的优先级更高，a做根节点，a原本的的右孩子和b竞争成为a的右孩子 
    {
        k = a;
        merge(tree[a].rc, tree[a].rc, b);
    } 
    else 
    {
        k = b;
        merge(tree[b].lc, a, tree[b].lc);
    }
    update(k);
    return ;
}
void insert(int &k, int val, int id, int ans) // 插入一个值为val的节点
{
    int a = 0, b = 0, cur = add_node(val, id, ans); //编号、权值、随机数、左右子结点数量 
    split(k, a, b, val);
    merge(a, a, cur); //merge(b, cur, b);
    merge(k, a, b); //merge(k, a, b);
    return ;
}
void get_ans(int k) //递归传标记，确保询问时标记都已经下传 
{
    if(k == 0)
        return ;
    pushdown(k);
    get_ans(tree[k].lc);
    get_ans(tree[k].rc);
    return ;
}
void reinsert(int &root, int cur) //将cur所在的树上节点暴力插入树root中 
{
    if(cur == 0)
        return ;
    pushdown(cur);
    insert(root, tree[cur].val, tree[cur].id, tree[cur].ans);
    reinsert(root, tree[cur].lc);
    reinsert(root, tree[cur].rc);
    return ;
}
void work(int val) //更新买得起价格val的衣服的信息 
{
    int a = 0, b = 0, c = 0;
    split(root, a, b, val - 1); //a树买不起 
    addtag(b, 1, val); //b树买得起打标记 
    split(b, c, b, 2 * val - 1); //c树重新插入 
    reinsert(a, c); //将c树插入a树 
    merge(root, a, b); 
    return ;
}
bool cmp(T_shirt x, T_shirt y)
{
    if(x.q != y.q)
        return x.q > y.q;
    return x.c < y.c;
}
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    srand(time(0));
    cin >> n;
    for(int i = 1; i <= n; i++)
        cin >> s[i].c >> s[i].q;
    sort(s + 1, s + n + 1, cmp);
    cin >> m;
    for(int i = 1; i <= m; i++)
    {
        int money;
        cin >> money;
        insert(root, money, i, 0);
    }
    for(int i = 1; i <= n; i++)
        work(s[i].c);
    get_ans(root);
    for(int i = 1; i <= m; i++)
        cout << ans[i] << " "; 
    return 0;
}

新的 split。

fhq-treap 的第二种 split 方法，按照节点的 size 劈开，适用于维护序列的下标。

如果把序列的下标作为权值维护平衡树，则平衡树的中序遍历即为原始序列的下标。

例题。

P3391 【模板】文艺平衡树

板子，上链接。

AC

P3224 [HNOI2012] 永无乡

给定 N 个点的排名（互不相同），在这些点间连边，问你从点 u 走到的排名第 k 小的点的编号。

排名，不难想到平衡树，直接用 FHQ-treap。

查询直接用板子，关键在于连边。

维护连通性，参考并查集。我们在维护树的节点的信息时加一个它在哪个连通块 rt，用并查集维护。

另外，考虑如何合并两棵平衡树。显然，我们把一棵树打散成单点（DFS 时左右子节点清零），一个一个暴力插入即可。然后维护并查集。

暴力插入，时间复杂度直接爆炸。考虑启发式合并，把小的那棵树插入到大的。因为插入后树的大小倍增，时间复杂度 O(\log N)，炸不了一点。

AC

P5338 [TJOI2019] 甲苯先生的滚榜

没什么好讲的，重写一个结构体表示题目通过数和罚时的结合，将 val-1 替换成 val.rib-1。

注意： last 不用重新赋值，查询的是排名 -1。

AC