首页 学习笔记

# 浅谈 fhq-treap（无旋treap）

模板题：洛谷 P6136 【模板】普通平衡树（数据加强版）

（emm刚写了这个，就放这个吧）

fhq−treapfhq-treap 也叫做 无旋treap，由范浩强大佬发明。

个人认为是平衡树中码量最少，也最容易理解的一种写法。

# 主要思想

顾名思义，无旋意味着它没有旋转操作（终于没有恶心人的旋转了）。

事实上，无旋treap只有两种操作。

一种是 splitsplit（分裂），另一种是 mergemerge（合并）。

平衡树中的各种操作都可以用这两个函数来搞定。下面我们来一一分析。

# 常见操作

  • 插入一个整数 xx

  • 删除一个整数 xx（若有多个相同的数，只删除一个）。

  • 查询整数 xx 的排名（排名定义为比当前数小的数的个数 +1）。

  • 查询排名为 xx 的数（如果不存在，则认为是排名小于 xx 的最大数。保证 xx 不会超过当前数据结构中数的总数）。

  • 求 xx 的前驱（前驱定义为小于 xx，且最大的数）。

  • 求 xx 的后继（后继定义为大于 xx，且最小的数）。

当然区间反转也是可以用无旋treaptreap 实现的，这里先不讲。

# 函数解释

# split（分裂）

splitsplit 函数要实现把一棵平衡树拆成两棵，左边的树上节点的值都小于等于 kk, 右边的树上节点的值都大于等于 kk。

  • x:x: 当前子树根节点

  • k:k: 以 kk 为分界线分割树

  • a,b:a, b: 分裂之后两棵子树的根，左边的子树根是 aa，右边的根是 bb，这里要传地址，方便写。

注意： 当根为 0 时，一定一定一定要清空 aa，&b&，不然会死循环（我就在这里卡了好久QWQ）

mark
1
2
3
4
5
6
7
8
9
10
11
12
13
14
inline void split(int x, int k, int &a, int &b){
    if(!x){
        a = b = 0;    //清空清空清空（重要的事情说三遍）
        return;
    }
    if(t[x].val <= k){
        a = x;        //左边子树已经分裂出去了，直接a=x
        split(rs(x), k, rs(x), b);    //在右子树上查找，把拆下来右子树上节点值<=k的点放回到x的右子树上
    }else{
        b = x;        //同理
        split(ls(x), k, a, ls(x));
    }
    pushup(x);
}

# merge（合并）

mergemerge 函数要实现把两个分开的树再合并到一起去，并返回合并后的根节点。

  • x,y:x, y: 两棵树的根

这个操作类似于线段树合并。

注意：合并时只能是两个相邻的子树合并，不能跳着合并。

例如：树 rtrt ---> 子树aa 和 子树bb

子树bb ---> 子树cc 和 子树dd （---> 表示拆成两棵树）

那么我们合并时，只能 merge(a,merge(c,d))merge(a, merge(c,d)) 或 merge(merge(a,c),d)merge(merge(a, c), d)。

而不能 merge(merge(a,d),c)merge(merge(a, d), c)

mark
1
2
3
4
5
6
7
8
9
10
11
12
inline int  merge(int x, int y){
    if(!x || !y) return x + y;
    if(t[x].wei <= t[y].wei){        //wei是随机值，wei(x) <= wei(y) 时，让 y 作为 x 的子树
        rs(x) = merge(rs(x), y);
        pushup(x);
        return x;
    }else{                            //反之，x 作为 y 的子树
        ls(y) = merge(x, ls(y));
        pushup(y);
        return y;
    }
}

# insert（插入）

先新建一个点设为 yy，把原树拆成 xx 和 zz。

xx 中节点值 <=k<= k，zz 中节点值 >k>k。

然后一次合并 xx，yy，zz即可。

mark
1
2
3
4
5
6
inline void insert(int k){
    t[++tot].val = k, t[tot].wei = rand();
    t[tot].siz = 1;
    split(root, k, a, b);
    root = merge(merge(a, tot), b);
}

# remove（删除）

这个就很巧妙了，我们把值 <=k<=k 的树先拆出来设为 aa，然后把值 <k<k 的点再拆出来，剩余的部分设为为 cc。

那么现在 cc 中的点就是 =k=k 的。

我们直接合并 cc 的左右两棵子树，这样就相当于把根节点删了。

最后合并回去。

mark
1
2
3
4
5
6
inline void remove(int k){
    split(root, k, a, b);        //拆，<=k的存到a里，>k的存到b里。
    split(a, k - 1, a, c);        //再拆，<k的存到a里，=k的存到里。
    c = merge(ls(c), rs(c));    //合并c左右子树
    root = merge(merge(a, c), b);    //再把a，b合并上去。
}

# check_rk

查询 kk 的排名。

我们把 <k<k 的的点从树上分裂出来，然后分出来的树的大小 +1 就是排名。

别忘了合并回去。

mark
1
2
3
4
5
6
7
inline int check_rk(int k){
    int rank;
    split(root, k - 1, a, b);
    rank = t[a].siz + 1;
    root = merge(a, b);
    return rank;
}

# check_val

查询排名为 kk 的数。

我这里用的递归写法。

  • xx 当前子树的根。

  • kk 在当前子树中排名多少。

我这里用的递归写法。（代码应该挺好理解的吧）

mark
1
2
3
4
5
inline int check_val(int x, int k){
    if(k == t[ls(x)].siz + 1) return t[x].val;
    if(k <= t[ls(x)].siz) return check_val(ls(x), k);    //在左子树中，直接跑左子树里查
    else return check_val(rs(x), k - t[ls(x)].siz - 1);    //在右子树中，减去左子树大小，再减1（根），就是在右子树中的排名。
}

# check_pre

查询前驱。

这个也好说，我们先查排名，设排名为 rkrk，我们再差排名为 rk−1rk - 1 的数是多少，就是前驱了。

mark
1
2
3
inline int check_pre(int x){
    return check_val(root, check_rk(x) - 1);
}

# check_next

查询 xx 的后继，基本同理，但略有不同。

因为 xx 可能有多个，我们查 xx 的排名后 +1，不一定是下一个数，有可能还是 xx。

那我们怎么办呢？

其实也不难，我们直接查 x+1x + 1 的排名，没有？没关系，就算没有 x+1x + 1，查出来的也是大于 xx 的最小的数的排名。

然后我们再查一下这个排名的值即可。

mark
1
2
3
inline int check_next(int x){
    return check_val(root, check_rk(x + 1));
}

然后……就没有然后了吧。

主函数我就不用多说了吧。

# 完整代码

mark
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstdlib>
#define ls(x) t[x].ch[0]
#define rs(x) t[x].ch[1]

using namespace std;

const int N = 2e6;        //原本的数+操作数。最多有1.1e6个数
struct Tree{
    int wei, val, siz, ch[2];
}t[N];
int n, m, tot, root;
int last, ans, a, b, c;

inline int read(){
    int x = 0, f = 1;
    char ch = getchar();
    while(ch < '0' || ch > '9') {if(ch == '-') f = -1; ch = getchar();}
    while(ch >= '0' && ch <= '9') x = (x << 3) + (x << 1) + ch - '0', ch = getchar();
    return x * f;
}

inline void pushup(int x){
    t[x].siz = t[ls(x)].siz + t[rs(x)].siz + 1;
}

inline void split(int x, int k, int &a, int &b){
    if(!x){
        a = b = 0;
        return;
    }
    if(t[x].val <= k){
        a = x;
        split(rs(x), k, rs(x), b);
    }else{
        b = x;
        split(ls(x), k, a, ls(x));
    }
    pushup(x);
}

inline int  merge(int x, int y){
    if(!x || !y) return x + y;
    if(t[x].wei <= t[y].wei){
        rs(x) = merge(rs(x), y);
        pushup(x);
        return x;
    }else{
        ls(y) = merge(x, ls(y));
        pushup(y);
        return y;
    }
}

inline void insert(int k){
    t[++tot].val = k, t[tot].wei = rand();
    t[tot].siz = 1;
    split(root, k, a, b);
    root = merge(merge(a, tot), b);
}

inline void remove(int k){
    split(root, k, a, b);
    split(a, k - 1, a, c);
    c = merge(ls(c), rs(c));
    root = merge(merge(a, c), b);
}

inline int check_rk(int k){
    int rank;
    split(root, k - 1, a, b);
    rank = t[a].siz + 1;
    root = merge(a, b);
    return rank;
}

inline int check_val(int x, int k){
    if(k == t[ls(x)].siz + 1) return t[x].val;
    if(k <= t[ls(x)].siz) return check_val(ls(x), k);
    else return check_val(rs(x), k - t[ls(x)].siz - 1);
}

inline int check_pre(int x){
    return check_val(root, check_rk(x) - 1);
}

inline int check_next(int x){
    return check_val(root, check_rk(x + 1));
}

int main(){
    n = read(), m = read();
    for(int i = 1; i <= n; i++){
        int x;
        x = read();
        insert(x);
    }
    while(m--){
        int op, x;
        op = read(), x = read() ^ last;
        if(op == 1) insert(x);
        if(op == 2) remove(x);
        if(op <= 2) continue;
        if(op == 3) last = check_rk(x);
        if(op == 4) last = check_val(root, x);
        if(op == 5) last = check_pre(x);
        if(op == 6) last = check_next(x);
        ans ^= last;
    }
    printf("%d\n", ans);
    return 0;
}

# End