BZOJ - 3224 Tyvj 1728 普通平衡树

Posted on | In , ,

思路

Treap模板题

Treap

Treap是一种二叉查找树，并同时满足了二叉树和堆的性质。每次插入一个值的时候，如果我们新建了一个树上的点，我们给这个点赋一个随机值，然后通过旋转等操作来维护Treap堆的性质，保证了树高期望是O(logn)，从而保证了时间复杂度。
通常来说Treap在常数大小和代码复杂度上要小于Splay。

节点定义

常规情况下Treap的节点需要储存左右儿子，子树大小，节点中相同元素的数量，随机数的值，我因为在treap结构体中定义了一个nexts的二维数组，所以node中没有写lson,rson。

1
2
3
4
5
template <typename T>
struct node{
    T val;
    int siz,rnd,cnt;
};

节点信息更新

更新最基本的子树大小以及一些其他内容，时间复杂度O(1)

1
2
3
void push_up(int k){
    tree[k].siz=tree[nexts[k][0]].siz+tree[nexts[k][1]].siz+tree[k].cnt;
}

旋转

与常见二叉树旋转类似，见参考中的详细解释

插入

从根开始，比根的val小进入左儿子，不然进入右儿子，如果值相等重复计数器cnt++。如果该节点尚未被创建，则初始化一个新节点放到当前位置。时间复杂度O(logn)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
void ins(int &p,int x){
        if(p==0){
            tree[nodecnt].siz=tree[nodecnt].cnt=1,tree[nodecnt].val=x,tree[nodecnt].rnd=rand();
            p=nodecnt++;
            return;
        }
        tree[p].siz++;
        if(tree[p].val==x)tree[p].cnt++;
        else if(x>tree[p].val){
            ins(nexts[p][1],x);
            if(tree[nexts[p][1]].rnd<tree[p].rnd)rotation(p,0);
        }
        else{
            ins(nexts[p][0],x);
            if(tree[nexts[p][0]].rnd<tree[p].rnd)rotation(p,1);
        }
    }

删除

如果删除值小于当前值，进入左子树，大于进入右子树
当等于时：
如果出现次数cnt大于1，cnt—
不然我们就要删除该节点，并分三种情况讨论：

  1. 没有左和右儿子，直接删除
  2. 有左或右儿子，用该儿子替换该节点
  3. 有左和右儿子，旋转并进入当前节点旋转后的位置，直到变成2的情况

时间复杂度O(logn)

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
void del(int &p,int x){
        //since through the data of bzoj we can find that x may not exist
        if(p==0)return;
        if(tree[p].val==x){
            if(tree[p].cnt>1)tree[p].cnt--,tree[p].siz--;
            else{
                if(nexts[p][0]==0||nexts[p][1]==0)p=nexts[p][0]+nexts[p][1];
                else if(tree[nexts[p][0]].rnd<tree[nexts[p][1]].rnd){
                    rotation(p,1);
                    del(p,x);
                }
                else{
                    rotation(p,0);
                    del(p,x);
                }
            }
        }
        else if(tree[p].val<x){
            tree[p].siz--;
            del(nexts[p][1],x);
        }
        else{
            tree[p].siz--;
            del(nexts[p][0],x);
        }
    }

查询数字x的排名

递归查询，并记录小于这个值的节点数量，时间复杂度O(logn)

1
2
3
4
5
6
int findRank(int p,int x){
        if(p==0)return 0;
        if(tree[p].val==x)return tree[nexts[p][0]].siz+1;
        else if(tree[p].val<x)return tree[nexts[p][0]].siz+tree[p].cnt+findRank(nexts[p][1],x);
        else return findRank(nexts[p][0],x);
    }

查询排名为x的数

与查排名思路相同

1
2
3
4
5
6
T findKey(int p,int x){
        if(p==0)return 0;
        if(tree[nexts[p][0]].siz>=x)return findKey(nexts[p][0],x);
        else if(tree[nexts[p][0]].siz+tree[p].cnt<x)return findKey(nexts[p][1],x-tree[nexts[p][0]].siz-tree[p].cnt);
        else return tree[p].val;
    }

查找前驱和后继

相同思路

1
2
3
4
5
6
7
8
9
10
11
T findPre(int p,int x){
        if(p==0)return -INF;
        if(tree[p].val<x)return max(tree[p].val,findPre(nexts[p][1],x));
        else return findPre(nexts[p][0],x);
    }
    //find the minimum number that larger than x
    T findNext(int p,int x){
        if(p==0)return INF;
        if(tree[p].val>x)return min(tree[p].val,findNext(nexts[p][0],x));
        else return findNext(nexts[p][1],x);
    }

参考

关于Treap学习总结
总结-Treap

代码

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
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
#include <bits/stdc++.h>
#define ll long long
#define INF 0x7fffffff
#define ms(a,val) memset((a),(val),(sizeof(a)))

using namespace std;

const int MAXN=100005;

template <typename T>
struct node{
    T val;
    int siz,rnd,cnt;
};
template <typename T>
struct treap{
    node<T> tree[MAXN];
    int nexts[MAXN][2],root,nodecnt;
    void init(){
        ms(nexts,0);
        root=0,nodecnt=1;
    }
    //maintain the data of the node like size
    void push_up(int k){
        tree[k].siz=tree[nexts[k][0]].siz+tree[nexts[k][1]].siz+tree[k].cnt;
    }
    //0->left,1->right
    void rotation(int &k,int dir){
        int v=nexts[k][dir^1];
        nexts[k][dir^1]=nexts[v][dir];
        nexts[v][dir]=k;
        push_up(k);
        push_up(k=v);//help us change the root
    }
    //& in order to change the l/r son
    void ins(int &p,int x){
        if(p==0){
            tree[nodecnt].siz=tree[nodecnt].cnt=1,tree[nodecnt].val=x,tree[nodecnt].rnd=rand();
            p=nodecnt++;
            return;
        }
        tree[p].siz++;
        if(tree[p].val==x)tree[p].cnt++;
        else if(x>tree[p].val){
            ins(nexts[p][1],x);
            if(tree[nexts[p][1]].rnd<tree[p].rnd)rotation(p,0);
        }
        else{
            ins(nexts[p][0],x);
            if(tree[nexts[p][0]].rnd<tree[p].rnd)rotation(p,1);
        }
    }
    void del(int &p,int x){
        //since through the data of bzoj we can find that x may not exist
        if(p==0)return;
        if(tree[p].val==x){
            if(tree[p].cnt>1)tree[p].cnt--,tree[p].siz--;
            else{
                if(nexts[p][0]==0||nexts[p][1]==0)p=nexts[p][0]+nexts[p][1];
                else if(tree[nexts[p][0]].rnd<tree[nexts[p][1]].rnd){
                    rotation(p,1);
                    del(p,x);
                }
                else{
                    rotation(p,0);
                    del(p,x);
                }
            }
        }
        else if(tree[p].val<x){
            tree[p].siz--;
            del(nexts[p][1],x);
        }
        else{
            tree[p].siz--;
            del(nexts[p][0],x);
        }
    }
    //query the rank of x
    int findRank(int p,int x){
        if(p==0)return 0;
        if(tree[p].val==x)return tree[nexts[p][0]].siz+1;
        else if(tree[p].val<x)return tree[nexts[p][0]].siz+tree[p].cnt+findRank(nexts[p][1],x);
        else return findRank(nexts[p][0],x);
    }
    //query the number ranked x
    T findKey(int p,int x){
        if(p==0)return 0;
        if(tree[nexts[p][0]].siz>=x)return findKey(nexts[p][0],x);
        else if(tree[nexts[p][0]].siz+tree[p].cnt<x)return findKey(nexts[p][1],x-tree[nexts[p][0]].siz-tree[p].cnt);
        else return tree[p].val;
    }
    //find the maximum number that smaller than x
    T findPre(int p,int x){
        if(p==0)return -INF;
        if(tree[p].val<x)return max(tree[p].val,findPre(nexts[p][1],x));
        else return findPre(nexts[p][0],x);
    }
    //find the minimum number that larger than x
    T findNext(int p,int x){
        if(p==0)return INF;
        if(tree[p].val>x)return min(tree[p].val,findNext(nexts[p][0],x));
        else return findNext(nexts[p][1],x);
    }
};
treap<int> tp;

int main() {
    int n;
    while(~scanf("%d",&n)){
        tp.init();
        for(int i=0;i<n;i++){
            int cho,val;
            scanf("%d%d",&cho,&val);
            switch(cho){
                case 1:
                    tp.ins(tp.root,val);
                    break;
                case 2:
                    tp.del(tp.root,val);
                    break;
                case 3:
                    printf("%d\n",tp.findRank(tp.root,val));
                    break;
                case 4:
                    printf("%d\n",tp.findKey(tp.root,val));
                    break;
                case 5:
                    printf("%d\n",tp.findPre(tp.root,val));
                    break;
                case 6:
                    printf("%d\n",tp.findNext(tp.root,val));
                    break;
            }
        }
    }
	return 0;
}