[模板] FHQ Treap 与可持久化平衡树

引言

Treap 和 Splay 是两种常用的平衡树，它们都通过旋转来保证树的平衡，从而使得内粗查询的复杂度为均摊 $O(\log n)$

但是正是因为它们需要旋转来保证时间复杂度，在可持久化平衡树时给我们带来了麻烦，而 FHQ Treap 是一种非旋转二叉树，它基于函数式编程的思想，由 split 和 merge 维护平衡树

Split

将一个平衡树按照权值 $k$ 分裂成两棵平衡树，一部分权值均小于等于 $k$，一部分权值大于 $k$

inline void split(int root, int k, int &x, int &y){
    if(!root){
        x = y = 0;
        return;
    }

    if(node[root].val <= k){
        x = root;
        split(rson(root), k, rson(x), y);
    }else{
        y = root;
        split(lson(root), k, x, lson(y));
    }

    update(root);
}

Merge

将两个平衡树合并为一棵树，其中 $x$ 树中每个数均小于等于 $y$ 树，那么按照随机附加域的大小进行合并

inline void merge(int &root, int x, int y){
    if(x == 0 || y == 0){
        root = x + y;
        return;
    }

    if(node[x].rd < node[y].rd){
        root = x;
        merge(rson(x), rson(x), y);
    }else{
        root = y;
        merge(lson(y), x, lson(y));
    }

    update(root);
}

插入

先按照要插入的权值分裂成 $x$ 和 $y$ 两部分，新建节点 $t$，将 $x$ 与 $t$ 合并，再与 $y$ 合并

inline int newnode(int x){
    node[++tot].siz = 1;
    node[tot].val = x;
    node[tot].rd = Random::rand(INT_MAX);
    lson(tot) = rson(tot) = 0;

    return tot;
} 

inline void insert(int val){
    int x = 0, y = 0;
    int nnode = newnode(val);

    split(root, val, x, y);
    merge(x, x, nnode);
    merge(root, x, y);
}

删除

从平衡树中删除一个权值为 $v$ 的节点，现将平衡树按照权值 $v$ 分为 $x$ 和 $y$ 两部分，再将平衡树 $x$ 按照 $v-1$ 分为 $x$ 和 $z$ 两部分，那么平衡树 $z$ 的所有节点权值都为 $v$，直接合并它的左子树和右子树即可，最后再依次合并复原。

inline void Delete(int val){
    int x = 0, y = 0, z = 0;

    split(root, val, x, y);
    split(x, val-1, x, z);

    merge(z, lson(z), rson(z));
    merge(x, x, z);
    merge(root, x, y);
}

查询第 $k$ 大

和正常的平衡树操作一样，通过递归的方式进行查询

inline int rank(int root, int k){
    int pos = root;

    while(true){
        if(node[lson(pos)].siz >= k){
            pos = lson(pos);
            continue;
        }

        k -= node[lson(pos)].siz;

        if(k <= 1){
            return node[pos].val;
        }

        k -= 1;

        pos = rson(pos);
    }
}

查询排名

查询第一个权值为 $v$ 的节点的排名即为按照 $v-1$ 分裂成 $x$ 和 $y$ 两棵子树，然后求出 $x$ 子树节点个数后加 $1$

inline int find(int val){
    int x = 0, y = 0;

    split(root, val - 1, x, y);
    int tmp = node[x].siz + 1;
    merge(root, x, y);

    return tmp;
} 

查询前驱

按照权值 $v – 1$ 分为子树 $x$ 和子树 $y$，查询子树 $x$ 中排名最后的数

inline int Pre(int val){
    int x = 0, y = 0;
    split(root, val - 1, x, y);
    int tmp = rank(x, node[x].siz);
    merge(root, x, y);

    return tmp;

}

查询后继

按照权值 $v$ 分为子树 $x$ 和子树 $y$，查询子树 $y$ 中排名第 $1$ 的数

inline int Next(int val){
    int x = 0, y = 0;
    split(root, val, x, y);
    int tmp = rank(y, 1);
    merge(root, x, y);
    return tmp;
}

完整模板

// https://www.luogu.org/problemnew/show/P3369
// Luogu 3369 普通平衡树

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <climits>
#include <algorithm>

using namespace std;
const int MAXN = 100000 + 10;

namespace Random{
    long long seed;

    inline void srand(int n){
        seed = n;
    }

    inline long long rand(int n){
        return seed = (seed * 20020905 % n) + 1; 
    }
}

using Random::rand;

namespace Treap{

    struct Node{
        int son[2];
        int val, siz, rd;   
    };  

    Node node[MAXN];

    int tot = 0;
    int root = 0;

    #define lson(x) node[x].son[0]
    #define rson(x) node[x].son[1]

    inline void update(int x){
        node[x].siz = node[lson(x)].siz + node[rson(x)].siz + 1;
    }

    inline void merge(int &root, int x, int y){
        if(x == 0 || y == 0){
            root = x + y;
            return;
        }

        if(node[x].rd < node[y].rd){
            root = x;
            merge(rson(x), rson(x), y);
        }else{
            root = y;
            merge(lson(y), x, lson(y));
        }

        update(root);
    }

    inline void split(int root, int k, int &x, int &y){
        if(!root){
            x = y = 0;
            return;
        }

        if(node[root].val <= k){
            x = root;
            split(rson(root), k, rson(x), y);
        }else{
            y = root;
            split(lson(root), k, x, lson(y));
        }

        update(root);
    }

    inline int newnode(int x){
        node[++tot].siz = 1;
        node[tot].val = x;
        node[tot].rd = Random::rand(INT_MAX);
        lson(tot) = rson(tot) = 0;

        return tot;
    } 

    inline void insert(int val){
        int x = 0, y = 0;
        int nnode = newnode(val);

        split(root, val, x, y);
        merge(x, x, nnode);
        merge(root, x, y);
    }

    inline void Delete(int val){
        int x = 0, y = 0, z = 0;

        split(root, val, x, y);
        split(x, val-1, x, z);

        merge(z, lson(z), rson(z));
        merge(x, x, z);
        merge(root, x, y);
    }

    inline int rank(int root, int k){
        int pos = root;

        while(true){
            if(node[lson(pos)].siz >= k){
                pos = lson(pos);
                continue;
            }

            k -= node[lson(pos)].siz;

            if(k <= 1){
                return node[pos].val;
            }

            k -= 1;

            pos = rson(pos);
        }
    }

    inline int find(int val){
        int x = 0, y = 0;

        split(root, val - 1, x, y);
        int tmp = node[x].siz + 1;
        merge(root, x, y);

        return tmp;
    } 

    inline int Pre(int val){
        int x = 0, y = 0;
        split(root, val - 1, x, y);
        int tmp = rank(x, node[x].siz);
        merge(root, x, y);

        return tmp;

    }

    inline int Next(int val){
        int x = 0, y = 0;
        split(root, val, x, y);
        int tmp = rank(y, 1);
        merge(root, x, y);
        return tmp;
    }

    #undef lson
    #undef rson

}

int main(){
    Random::srand(19260817);

    int n;
    scanf("%d",&n);

    for(int i=0; i<n; i++){
        int op,id;
        scanf("%d%d",&op,&id);

        if(op==1)
            Treap::insert(id);
        else if(op==2)
            Treap::Delete(id);
        else if(op==3)
            printf("%d\n",Treap::find(id));
        else if(op==4)
            printf("%d\n",Treap::rank(Treap::root, id));
        else if(op==5){
            printf("%d\n",Treap::Pre(id));
        }else{
            printf("%d\n",Treap::Next(id));
        }
    }
    return 0;
}

可持久化

因为 FHQ Treap 不需要旋转，因此可以支持可持久化，与其他可持久化数据结构一样，我们使用一个 root 数组来表示不同版本对应的根

FHQ Treap 的持久化只需要在 Split 过程中，基于原树复制一个一样的节点，再进行操作

inline int copynode(int root){
    node[++tot] = node[root];
    return tot;
}

inline void split(int oldroot, int k, int &x, int &y){
    if(!oldroot){
        x = y = 0;
        return;
    }

    int root = copynode(oldroot);

    if(node[root].val <= k){
        x = root;
        split(rson(root), k, rson(root), y);
    }else{
        y = root;
        split(lson(root), k, x, lson(y));
    }

    update(root);
}

可持久化平衡树模板

// https://www.luogu.org/problemnew/show/P3835
// Luogu 3835 可持久化平衡树

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <climits>
#include <algorithm>

using namespace std;
const int MAXN = 500000 + 10;

namespace Random{
    long long seed;

    inline void srand(long long n){
        seed = n;
    }

    inline int rand(){
        return seed = (seed * 20020905 % INT_MAX) + 1;
    }
}

namespace Treap{
    struct Node{
        int son[2];
        int val, siz, rd;
    };

    Node node[MAXN << 5];
    int tot;

    #define lson(x) node[x].son[0]
    #define rson(x) node[x].son[1]

    inline void update(int x){
        node[x].siz = node[lson(x)].siz + node[rson(x)].siz + 1;    
    }

    inline int newnode(int key){
        node[++tot].val = key;
        node[tot].rd = Random::rand();
        node[tot].siz = 1;

        return tot;
    }

    inline int copynode(int root){
        node[++tot] = node[root];
        return tot;
    }

    inline void split(int oldroot, int k, int &x, int &y){
        if(!oldroot){
            x = y = 0;
            return;
        }

        int root = copynode(oldroot);

        if(node[root].val <= k){
            x = root;
            split(rson(root), k, rson(root), y);
        }else{
            y = root;
            split(lson(root), k, x, lson(y));
        }

        update(root);
    }

    inline void merge(int &root, int x, int y){
        if(x == 0 || y == 0){
            root = x + y;
            return;
        }

        if(node[x].rd < node[y].rd){
            root = x;
            merge(rson(x), rson(x), y);
        }else{
            root = y;
            merge(lson(y), x, lson(y));
        }

        update(root);
    }

    inline void insert(int& root, int val){
        int nnode = newnode(val);
        int x = 0, y = 0;

        split(root, val, x, y);
        merge(x, x, nnode);
        merge(root, x, y);
    }

    inline void Delete(int& root, int val){
        int x = 0, y = 0, z = 0;

        split(root, val, x, y);
        split(x, val - 1, x, z);
        merge(z, lson(z), rson(z));
        merge(x, x, z);
        merge(root, x, y);
    }

    inline int find(int& root, int val){
        int x = 0, y = 0;

        split(root, val-1, x, y);
        int tmp = node[x].siz + 1;
        merge(root, x, y);

        return tmp;
    }

    inline int rank(int& root, int val){
        int pos = root;

        while(pos){
            if(node[lson(pos)].siz >= val){
                pos = lson(pos);
                continue;
            }

            val -= node[lson(pos)].siz;

            if(val <= 1){
                return node[pos].val;
            }

            val -= 1;
            pos = rson(pos);
        }   
    }

    inline int Pre(int& root, int val){
        int x = 0, y = 0;

        split(root, val - 1, x, y);
        int tmp = rank(x, node[x].siz);
        merge(root, x, y);

        return tmp;
    }

    inline int Next(int& root, int val){
        int x = 0, y = 0;

        split(root, val, x, y);
        int tmp = rank(y, 1);
        merge(root, x, y);

        return tmp;
    }

    #undef lson
    #undef rson
}

int root[MAXN];

int main(){
    Random::srand(19260817);

    int n;
    scanf("%d",&n);

    Treap::insert(root[0], 2147483647);
    Treap::insert(root[0], -2147483647);

    for(int i=1; i<=n; i++){
        int old,op,id;
        scanf("%d%d%d",&old, &op,&id);

        root[i] = root[old];

        if(op==1)
            Treap::insert(root[i], id);
        else if(op==2)
            Treap::Delete(root[i], id);
        else if(op==3)
            printf("%d\n",Treap::find(root[i], id) - 1);
        else if(op==4)
            printf("%d\n",Treap::rank(root[i], id + 1));
        else if(op==5){
            printf("%d\n",Treap::Pre(root[i], id));
        }else{
            printf("%d\n",Treap::Next(root[i], id));
        }
    }
    return 0;
}