FHQ/无旋平衡树

11490DX Re: Master Lv.15
  2024-10-31 18:25:58 2024-10-31 18:25:58 Created   2025-02-18 07:24:23 2025-02-18 07:24:23 Updated      4.5k Words  22 Mins  

 

这个平衡树似乎是对新手最友好的平衡树（至少比Splay友好）但似乎又不友好

众所周知，平衡树是一个可以高效进行查找操作的二叉树。一个以值域为关键字的平衡树的节点左边子树的值肯定都比这个点小，右边子树的值肯定都比这个点大。平衡树可以实现插入、删除、查找排名、前驱、后继等等功能。而 FHQ Treap 则只用到分裂和合并两个操作。

img
（图为一棵普通的平衡树）

分裂

基本函数：void split(int x, int bas, int &l, int &r)。这个函数执行把以 为根的树按照值 进行分裂，小于等于 的放到左树，大于 的放到右树。并且左树和右树也是两棵平衡树。 和 就分别返回了左树和右树的根。

函数代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
void split(int x, int bas, int &L, int &R){
        if(x == 0){ //如果到了叶子节点的下一层（就没有可分的了）
            L = R = 0; //那么就返回
            return ;
        }
        if(tr[x].val <= bas){ //如果这个根节点的值小于等于bas
            L = x; //那么就只用搜索右子树，因为左子树的所有值都是小于等于bas。设这个节点为左子树的根
            split(tr[x].rs, bas, tr[x].rs, R); //那么就只用搜索右子树。tr[x].rs是预留给右子树的点
        }else{//否则右子树的所有节点值都大于bas。右树的右子树就确定了。接下来就只用预留右树的左子树。
            R = x;
            split(tr[x].ls, bas, L, tr[x].ls);
        }
    }

img
（图为分裂一棵树的可视化）

合并

个人觉得合并理解起来比分裂简单的很多。基本函数：int merge(int l, int r)，合并以 和 为根的两棵平衡树，再返回这一棵大平衡树的根。这里依据的则是随机分配的优先级。也就是怎么合并完全是随机的。这样才能使复杂度均摊到 。合并的隐含条件是以 为根的这颗平衡树的所有节点的值都要小于以 为根的所有节点的值。

函数代码：

1
2
3
4
5
6
7
8
9
10
11
12
int merge(int L, int R){
        if(L == 0 || R == 0) return L+R; //如果有一个搜完了，那么就没必要继续往下搜了，直接把另外一棵树没有搜的部分合并到现在这颗点的下面。
        if(tr[L].pri > tr[R].pri){//如果左树的优先级大于右树的优先级
            tr[L].rs = merge(tr[L].rs, R);
            //我们知道 左树的右子树 和 右树的所有节点 都是大于左树的所有节点的。那么我们就把左树的左子树固定到新树上，接下来就是 左树的右子树 和 右树 合并了。
            return L; //以L为根
        }else{
            tr[R].ls = merge(L, tr[R].ls);
            //同理，右树的左子树 和 左树的所有节点都是小于右树的所有节点的，那么我们就把右树的右子树固定到新树上，接下来就是 左树 和 右树的左子树 合并了。
            return R; //以R为根
        }
    }

img
（图为合并一棵树的可视化）

只要理解了这两个操作，其他的操作都是简单的。

其他操作：

  • 插入值 ：将树以值 分裂为两棵树，再将 插入左树，再把左树和右树合并。
  • 删除值 ：分两种情况：
    • 若有多个则只删除一个 ，其他 保留：分裂出小于 ，等于 ，大于 这三棵平衡树，将等于 的这一棵的左子树和右子树合并，这样就消掉了他的根，大小刚刚好 ，再分别合并这三棵树。
    • 若有多个 则全删除：分裂出小于 ，等于 ，大于 这三棵树，将小于 和大于 这两棵树合并。这样等于 的这一棵树（可能有多个元素）就被完全消掉了！
  • 求数 的排名（小于 的数的个数 ）：这个要记录以每个节点为根的子树的大小。定义这个变量为 siz。把他塞到每个节点的结构体里。每次更新的时候再更新一下当前节点的 siz 大小：tr[x].siz = tr[tr[x].ls].siz + tr[tr[x].rs].siz + 1。查找排名即分裂出小于等于 （即小于 ）和大于等于 的两棵树，然后排名就是小于 的那棵树的 。
  • 求第 大数：看这个根的左子树的大小，记其为 。若 ，那就说明第 大数就是根，就返回根。若 ，说明第 大数在左子树里，指针指向左子树的根，继续求第 大数。若 ，说明第 大数在右子树里，指针指向右子树的根，因为这个右子树没有记这个左子树和这个根，并且根据平衡树的性质，右子树的每一个数一定比左子树的每一个数和根大。那么就查找右子树的排名第 的数即可。递归求即可。
  • 求数 的前驱（第一个比 小的数）：分裂为小于等于 （小于 ）和大于等于 的两棵树，记小于等于 的树的大小为 ，那就找这棵树的第 大数即可。
  • 求数 的后继（第一个比 大的数）：分裂为小于等于 的和大于 的两棵树，求大于 的这棵树的第 大（排名为 ）数即可。

例题：P3369【模板】普通平衡树

操作即为上述操作。

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
#include<bits/stdc++.h>
using namespace std;
const int N = 1e5+6;
mt19937 rnd(time(0));
struct FHQTreap{
    struct node{
        int ls, rs, val, pri, siz;
    }tr[N];
    int idx=0, rt=0;
    void newnode(int val){
        tr[++idx].pri = rnd();
        tr[idx].ls = tr[idx].rs = 0;
        tr[idx].siz = 1;
        tr[idx].val = val;
    }
    void update(int x){
        tr[x].siz = tr[tr[x].ls].siz + tr[tr[x].rs].siz + 1;
    }
    void split(int x, int bas, int &L, int &R){
        if(x == 0){
            L = R = 0;
            return ;
        }
        if(tr[x].val <= bas){
            L = x;
            split(tr[x].rs, bas, tr[x].rs, R);
        }else{
            R = x;
            split(tr[x].ls, bas, L, tr[x].ls);
        }
        update(x);
    }
    int merge(int L, int R){
        if(L == 0 || R == 0) return L+R;
        if(tr[L].pri > tr[R].pri){
            tr[L].rs = merge(tr[L].rs, R);
            update(L);
            return L;
        }else{
            tr[R].ls = merge(L, tr[R].ls);
            update(R);
            return R;
        }
    }
    void insert(int x){
        int l, r;
        split(rt, x, l, r);
        newnode(x);
        l = merge(l, idx);
        rt = merge(l, r);
    }
    void del(int x){
        int l, r;
        split(rt, x, l, r);
        int ismid;
        split(l, x-1, l, ismid);
        ismid = merge(tr[ismid].ls, tr[ismid].rs);//这里行得通是因为这个操作只删了值为x的treap中的根（因为树=根+左儿子+右儿子），就相当于只删除了一个数！
        rt = merge(merge(l, ismid), r);
        //rt = merge(l, r);这句不行！因为这一句把所有值为x的数全部都删除了！
    }
    int kth(int x, int rk){//kth
        int lftsiz = tr[tr[x].ls].siz;
        if(rk == lftsiz + 1){
            return x;
        }
        if(rk <= lftsiz){
            return kth(tr[x].ls, rk);
        }else return kth(tr[x].rs, rk - lftsiz - 1);
    }
    void getnum(int x){
        cout<<tr[kth(rt, x)].val<<'\n';
    }
    void getrk(int x){
        int l, r;
        split(rt, x-1, l, r);
        cout<<tr[l].siz + 1<<'\n';
        rt = merge(l, r);
    }
    void getpre(int x){
        int l, r;
        split(rt, x-1, l, r);
        cout<<tr[kth(l, tr[l].siz)].val<<'\n';
        rt = merge(l, r);
    }
    void getsuf(int x){
        int l, r;
        split(rt, x, l, r);
        cout<<tr[kth(r, 1)].val<<'\n';
        rt = merge(l, r);
    }
}treap;
int main(){
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
    int q;
    cin>>q;
    int op, x;
    while(q--){
        cin>>op>>x;
        switch(op){
            case 1: treap.insert(x); break;
            case 2: treap.del(x); break;
            case 3: treap.getrk(x); break;
            case 4: treap.getnum(x); break;
            case 5: treap.getpre(x); break;
            case 6: treap.getsuf(x); break;
        }
    }
    return 0;
}

P4008 文本编辑器

这个分裂就不是按照权值分裂，而是按照排名分裂。按照排名分裂的思路就相当于是把 分裂 操作 和 求第k大数 结合起来。这里的 就不再是一个固定值了。

Split 操作代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
void split(int x, int bas, int &l, int &r){ //这个是小于等于排名bas的分到左树，大于排名bas的分到右树
        if(x==0){
            l=r=0; return ;
        }
        if(tr[tr[x].ls].siz+1<=bas){ //如果左树的大小+1（就是根的排名）小于等于要求排名bas
            l = x;//那么就说明那个排名为bas的在右子树，就可以把左子树定下来。
            split(tr[x].rs, bas - tr[tr[x].ls].siz - 1, tr[x].rs, r); //搜索右子树，bas也应该减去左子树和根的siz
        }else{ //否则同理
            r = x;
            split(tr[x].ls, bas, l, tr[x].ls);
        }
        pushup(x); //更新siz
    }

其他的都和上述操作一样。

这里的输出是根据排名用中序遍历输出，即“左根右”。这样就保证了我们输出的排名是单调递增的。

注意到使用 getchar 时不能开 ios::sync_with_stdio(0), cin.tie(0), cout.tie(0)！

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
#include<bits/stdc++.h>
using namespace std;
const int N = 2e6+6;
mt19937 rnd(time(0));
int idx = 0, rt = 0;
struct FHQTreap{
    struct node{
        int ls, rs, siz, pri;
        char val;
    }tr[N];
    
    void pushup(int x){
        tr[x].siz = tr[tr[x].ls].siz + tr[tr[x].rs].siz + 1;
    }
    void newnode(char x){
        tr[++idx].val = x;
        tr[idx].ls = tr[idx].rs = 0;
        tr[idx].pri = rnd();
        tr[idx].siz = 1;
    }
    void split(int x, int bas, int &l, int &r){
        if(x==0){
            l=r=0; return ;
        }
        if(tr[tr[x].ls].siz+1<=bas){
            l = x;
            split(tr[x].rs, bas - tr[tr[x].ls].siz - 1, tr[x].rs, r);
        }else{
            r = x;
            split(tr[x].ls, bas, l, tr[x].ls);
        }
        pushup(x);
    }
    int merge(int l, int r){
        if(l==0 || r==0) return l+r;
        if(tr[l].pri > tr[r].pri){
            tr[l].rs = merge(tr[l].rs, r);
            pushup(l);
            return l;
        }else{
            tr[r].ls = merge(l, tr[r].ls);
            pushup(r);
            return r;
        }
    }
    void inorder(int x){//中序遍历
        if(x==0) return ;
        inorder(tr[x].ls);
        cout<<tr[x].val;
        inorder(tr[x].rs);
    }
}treap;
int q;
int main(){
    // ios::sync_with_stdio(0);
    // cin.tie(0), cout.tie(0);
    cin>>q;
    char s[10];
    int n;
    int pos = 0;
    int l, r;
    while(q--){
        cin>>(s+1);
        if(s[1] == 'I'){
            cin>>n;
            treap.split(rt, pos, l, r);
            for(int i=1;i<=n;i++){
                char c;
                c = getchar();
                while(c < 32 || c > 126) c = getchar();
                treap.newnode(c);
                l = treap.merge(l, idx);
            }
            rt = treap.merge(l, r);
        }else if(s[1] == 'M'){
            cin>>pos;
        }else if(s[1] == 'D'){
            cin>>n;
            int mid;
            treap.split(rt, pos, l, mid);
            treap.split(mid, n, mid, r);
            rt = treap.merge(l, r);
        }else if(s[1] == 'G'){
            cin>>n;
            int mid;
            treap.split(rt, pos, l, mid);
            treap.split(mid, n, mid, r);
            treap.inorder(mid);
            cout<<'\n';
            rt = treap.merge(treap.merge(l, mid), r);
        }else if(s[1] == 'P') pos--;
        else if(s[1] == 'N')pos++;
        // cerr<<q<<' '<<(s+1)<<' '<<pos<<'\n';
    }
    return 0;
}

P3391 文艺平衡树

这道题要求我们支持旋转的操作。考虑旋转该如何在一棵二叉树上进行。

这里给出的解释是先交换根 的左右儿子（就是左右树），再指向它的左儿子 ，再继续递归下去。完成后就指向 的右儿子 ，然后再这样递归下去。

把他搬到平衡树上，基本的 split 和 merge 就已经有这样的思想。那我们就只用记一个 lazytag，每次扫到这里的时候更新一下即可。交换区间 只需把 的树抽出来，再把它的根的 lazytag 亦或上 即可。

基本代码（只需一个 pushdown 即可）：

1
2
3
4
5
6
7
void pushdown(int x){
    if(tr[x].lazy){
        tr[x].lazy = 0;
        swap(tr[x].ls, tr[x].rs);
        tr[tr[x].ls].lazy ^= 1, tr[tr[x].rs].lazy ^= 1;
    }
}

其实发现这个 pushdown 和线段树里的是很像的。只要理解线段树这个应该不会太难。

把这个代码插到 split 函数和 merge 函数里。扫到这里的时候就 pushdown 更新一下。

img
（图为旋转一段区间（一棵树）的可视化）

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
#include<bits/stdc++.h>
using namespace std;
const int N = 1e5+6;

mt19937 rnd(time(0));
namespace FHQTreap{
    struct node{
        int ls, rs, val, siz, pri, lazy;
    }tr[N];
    int rt=0, idx=0;
    void newnode(int x){
        tr[++idx].val = x;
        tr[idx].ls = tr[idx].rs = 0;
        tr[idx].siz = 1;
        tr[idx].pri = rnd();
        tr[idx].lazy = 0;
    }
    void pushup(int x){
        tr[x].siz = tr[tr[x].ls].siz + tr[tr[x].rs].siz + 1;
    }
    void pushdown(int x){
        if(tr[x].lazy){
            tr[x].lazy = 0;
            swap(tr[x].ls, tr[x].rs);
            tr[tr[x].ls].lazy ^= 1, tr[tr[x].rs].lazy ^= 1;
        }
    }
    void split(int x, int bas, int &l, int &r){
        if(x == 0){
            l = r = 0;
            return ;
        }
        pushdown(x);
        if(tr[tr[x].ls].siz + 1 <= bas){
            l = x;
            split(tr[x].rs, bas - tr[tr[x].ls].siz - 1, tr[x].rs, r);
        }else{
            r = x;
            split(tr[x].ls, bas, l, tr[x].ls);
        }
        pushup(x);
    }
    int merge(int l, int r){
        if(l==0||r==0) return l+r;
        if(tr[l].pri > tr[r].pri){
            pushdown(l);
            tr[l].rs = merge(tr[l].rs, r);
            pushup(l);
            return l;
        }else{
            pushdown(r);
            tr[r].ls = merge(l, tr[r].ls);
            pushup(r);
            return r;
        }
    }
    void inorder(int x){
        if(x==0) return ;
        pushdown(x);
        inorder(tr[x].ls);
        cout<<tr[x].val<<' ';
        inorder(tr[x].rs);
    }
}
using namespace FHQTreap;
int n, m;
int main(){
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
    cin>>n>>m;
    for(int i=1;i<=n;i++){
        newnode(i);
        rt = merge(rt, idx);
    }
    int ql, qr;
    while(m--){
        cin>>ql>>qr;
        int l, r, mid;
        split(rt, qr, l, r);
        split(l, ql-1, l, mid);
        tr[mid].lazy ^= 1;
        rt = merge(merge(l, mid), r);
    }
    inorder(rt);
    return 0;
}

P5055 可持久化文艺平衡树

要做到可持久化，我们借鉴之前学的可持久化线段树的思维，记录一个 数组，存放每一个版本的根。动态开点之前已经实现了。我们再把空间开大（我开多少倍只能随缘，推荐开 倍）。

Split 操作时每次修改要记得新建一个节点，因为这是基于之前的版本改的。而且新建节点时要复制之前节点的全部信息。否则你将会获得五彩斑斓的好成绩。

这里要记录一个区间和，那么就在结构体里新建一个 sum 变量即可，再在 pushup 函数里更新一下就做完了。

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
115
#include<bits/stdc++.h>
using namespace std;
const int N = 2e5+5;
const int M = 200*N;
typedef long long ll;
mt19937 rnd(time(0));
namespace FHQTreap{
    struct node{
        int ls, rs, siz, val, pri, lazy;
        ll sum;
    }tr[M];
    int rt[N], idx;
    int newnode(int x){
        tr[++idx].siz = 1;
        tr[idx].sum = tr[idx].val = x;
        tr[idx].ls = tr[idx].rs = 0;
        tr[idx].pri = rnd(); 
        return idx;
    }
    void pushup(int x){
        tr[x].siz = tr[tr[x].ls].siz + tr[tr[x].rs].siz + 1;
        tr[x].sum = tr[tr[x].ls].sum + tr[tr[x].rs].sum + tr[x].val;
    }
    int clone(int x){
        newnode(0);
        tr[idx] = tr[x];
        return idx;
    }
    void pushdown(int x){
        if(tr[x].lazy){
            if(tr[x].ls) tr[x].ls = clone(tr[x].ls);
            if(tr[x].rs) tr[x].rs = clone(tr[x].rs);
            swap(tr[x].ls, tr[x].rs);
            tr[tr[x].ls].lazy ^= 1, tr[tr[x].rs].lazy ^= 1;
            tr[x].lazy = 0;
        }
    }
    void split(int x, int bas, int &l, int &r){
        if(x == 0){
            l = r = 0;
            return ;
        }
        pushdown(x);
        if(tr[tr[x].ls].siz + 1 <= bas){
            l = clone(x);
            split(tr[l].rs, bas - tr[tr[x].ls].siz - 1, tr[l].rs, r);
            pushup(l);
        }else{
            r = clone(x);
            split(tr[r].ls, bas, l, tr[r].ls);
            pushup(r);
        }
    }
    int merge(int l, int r){
        if(l==0||r==0){
            return l+r;
        }
        pushdown(l), pushdown(r);
        if(tr[l].pri > tr[r].pri){
            tr[l].rs = merge(tr[l].rs, r);
            pushup(l);
            return l;
        }else{
            tr[r].ls = merge(l, tr[r].ls);
            pushup(r);
            return r;
        }
    }
}
using namespace FHQTreap;
ll lastans = 0;
int q;
int main(){
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
    cin>>q;
    int op, v;
    ll p, x, ql, qr;
    int ver=0;
    while(q--){
        cin>>v>>op;
        if(op==1){
            cin>>p>>x;
            p ^= lastans, x ^= lastans;
            int l, r;
            split(rt[v], p, l, r);
            int pointidx = newnode(x);
            rt[++ver] = merge(merge(l, pointidx), r);                
        }else if(op == 2){
            cin>>p;
            p ^= lastans;
            int l, r, mid;
            split(rt[v], p, l, r);
            split(l, p-1, l, mid);
            rt[++ver] = merge(l, r);
        }else if(op == 3){
            cin>>ql>>qr;
            ql ^= lastans, qr ^= lastans;
            int l, r, mid;
            split(rt[v], qr, l, r);
            split(l, ql-1, l, mid);
            tr[mid].lazy = 1;
            rt[++ver] = merge(merge(l, mid), r);
        }else{
            cin>>ql>>qr;
            ql ^= lastans, qr ^= lastans;
            int l, r, mid;
            split(rt[v], qr, l, r);
            split(l, ql-1, l, mid);
            lastans = tr[mid].sum;
            cout<<lastans<<'\n';
            rt[++ver] = merge(merge(l, mid), r);
        }
    }
}

P3835 可持久化平衡树

这道题比上面那道题要简单，沿用上面那道题的可持久化思路就可以做了

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
115
116
117
118
119
120
121
122
123
#include<bits/stdc++.h>
using namespace std;
const int N = 5e5+6;
const int M = 100*N;
mt19937 rnd(time(0));
namespace FHQTreap{
    struct node{
        int ls, rs, val, siz, pri;
    }tr[M];
    int rt[N], idx = 0, ver = 0;
    int newnode(int x){
        tr[++idx].siz = 1;
        tr[idx].ls = tr[idx].rs = 0;
        tr[idx].val = x;
        tr[idx].pri = rnd();
        return idx;
    }
    int clone(int x){
        int pointidx = newnode(0);
        tr[pointidx] = tr[x];
        return pointidx;
    }
    void pushup(int x){
        tr[x].siz = tr[tr[x].ls].siz + tr[tr[x].rs].siz + 1;
    }
    void split(int x, int bas, int &l, int &r){
        if(x == 0){
            l = r = 0;
            return ;
        }
        if(tr[x].val <= bas){
            l = clone(x);
            split(tr[l].rs, bas, tr[l].rs, r);
            pushup(l);
        }else{
            r = clone(x);
            split(tr[r].ls, bas, l, tr[r].ls);
            pushup(r);
        }
    }
    int merge(int l, int r){
        if(l==0||r==0) return l+r;
        if(tr[l].pri > tr[r].pri){
            tr[l].rs = merge(tr[l].rs, r);
            pushup(l);
            return l;
        }else{
            tr[r].ls = merge(l, tr[r].ls);
            pushup(r);
            return r;
        }
    }
    void insert(int v, int x){
        int pointidx = newnode(x);
        int l, r;
        split(rt[v], x, l, r);
        rt[++ver] = merge(merge(l, pointidx), r);
    }
    void del(int v, int x){
        int l, r, mid;
        split(rt[v], x, l, r);
        split(l, x-1, l, mid);
        mid = merge(tr[mid].ls, tr[mid].rs);
        rt[++ver] = merge(merge(l, mid), r);
    }
    int getrnk(int v, int x){
        int l, r;
        split(rt[v], x-1, l, r);
        int ans = tr[l].siz + 1;
        rt[++ver] = merge(l, r);
        return ans;
    }
    int kth(int x, int k){
        // cerr<<tr[x].siz<<'\n';
        if(tr[tr[x].ls].siz+1==k) return tr[x].val;
        if(tr[tr[x].ls].siz>=k){
            return kth(tr[x].ls, k);
        }else return kth(tr[x].rs, k-tr[tr[x].ls].siz-1);
    }
    int getkth(int v, int k){
        int ans = kth(rt[v], k);
        rt[++ver] = rt[v];
        return ans;
    }
    int getpre(int v, int x){
        int l, r;
        split(rt[v], x-1, l, r);
        int ans = 0;
        if(tr[l].siz == 0) ans = -2147483647;
        else ans = kth(l, tr[l].siz);
        rt[++ver] = merge(l, r);
        return ans;
    }
    int getsuf(int v, int x){
        int l, r;
        split(rt[v], x, l, r);
        int ans = 0;
        if(tr[r].siz == 0) ans = 2147483647;
        else ans = kth(r, 1);
        rt[++ver] = merge(l, r);
        return ans;
    }
}
using namespace FHQTreap;
int q;
int main(){
    int v, op, x;
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
    cin>>q;
    while(q--){
        cin>>v>>op>>x;
        switch(op){
            case 1: insert(v, x);                 break;
            case 2: del(v, x);                    break;
            case 3: cout<<getrnk(v, x)<<'\n';     break;
            case 4: cout<<getkth(v, x)<<'\n';     break;
            case 5: cout<<getpre(v, x)<<'\n';     break;
            case 6: cout<<getsuf(v, x)<<'\n';     break;
        }
    }
    return 0;
}
  • Title: FHQ/无旋平衡树
  • Author: 11490DX
  • Created at : 2024-10-31 18:25:58
  • Updated at : 2025-02-18 07:24:23
  • Link: https://11490dx.net/2024/10/31/fhqtreap-sum/
  • License: This work is licensed under CC BY-NC-SA 4.0.
Comments
On this page
FHQ/无旋平衡树
  1. 分裂
  2. 合并
  3. 其他操作：
  • 例题：P3369【模板】普通平衡树
  • P4008 文本编辑器
  • P3391 文艺平衡树
  • P5055 可持久化文艺平衡树
  • P3835 可持久化平衡树