刚刚跟着em-lgh大佬学了非旋转treap

非常庆幸不用再写万恶的rotate了（来自高级数据结构的恶意）

来记一下

treap

概念

简单来说，(tree_{二叉搜索树} * heap_堆 = treap_{平衡树})

这显然不是袁隆平爷爷干的

二叉搜索树，堆←不懂请戳这里

显然这两样东西有各自的排列顺序——左小右大以及根小（大）儿子大（小）

对于寻找答案来讲，二叉搜索树更加方便

— 那么堆用来干嘛呢

很简单，用来达到期望平衡

— 怎么实现呢

通过另一个关键字

— 为什么是“期望”平衡呢

因为是通过随机的关键字啊！

操作

上面说过了，二叉搜索树管答案，堆管时间

李云龙：“你管生活，我管军事”

如何让随机的关键字满足堆的性质，同时节点的值满足二叉搜索树的性质呢

旋转

然而这个玩意十分难写且难理解。。。

所以就出现了……

非旋转treap

它与旋转的treap很相似

但是它是基于分裂和合并两个基本操作而不是旋转

-define表+struct，请对照此表理解代码-

#define lson t[x].ls #define rson t[x].rs #define si t[x].size #define ra t[x].ran #define lss t[t[x].ls].size #define rss t[t[x].rs].size #define va t[x].val //------------------------- struct node {     int val, size, ls, rs, ran; }t[100001]; 

新建节点

正常的初始化

inline void newnode(int &x, int val) {     ++tot;     t[tot].size=1;     t[tot].val=val;     t[tot].ran=rand();     t[tot].ls=t[tot].rs=0;     x=tot; }

分裂

指定一个val，将值∈[0, val]的节点与值∈(val, +∞)的节点分成两棵树

实现过程和寻找后继的过程很像

void split(int x, int &l, int &r, int val) {     if(!x)     {         l = r = 0;         return;     }     if(va <= val) l = x, split(t[x].rs, t[l].rs, r, val);//当前值比val小或等于val，则将它与它的左子树全部划分到第一棵树，继续寻找它的右子树     else r = x, split(t[x].ls, l, t[r].ls, val);//反之，则将它与它的右子树划分到第二棵树，寻找它的左子树     pushup(x);//不要忘记更新size }

合并

分裂的反过程

要求合并的a树与b树中(a_{max} < b_{min})

void merge(int &x, int a, int b) {     if(!a||!b)     {         x = a + b;         return;     }     if(t[a].ran < t[b].ran) x = a, merge(t[x].rs, t[a].rs, b);//随机值在这里用，用来在合并时维护堆的性质     else x = b, merge(t[x].ls, a, t[b].ls);     pushup(x);//更新！ }

插入

基于分裂和合并

在(val – 1)处分裂->合并节点z与树a->合并树a与树b

void insert(int val) {     int x = 0, y = 0, z = 0;     newnode(z, val);     split(root, x, y, val - 1);     merge(x, x, z);     merge(root, x, y); }

删除

和插入很像

将大树在(val – 1)处分裂成ab->将树b在(val)处分裂成bc->合并树a与树c

void del(int val) {     int x = 0, y = 0, z = 0;     split(root, x, y, val);     split(x, x, z, val - 1);     merge(z, t[z].ls, t[z].rs);//这里是只删除一个的操作，全部删除请忽略本行和下一行     merge(x, x, z);     merge(root, x, y); }

询问排名

和插入很像

在(val-1)处分裂->输出a的size

void ask_rank(int v) {     int x = 0, y = 0;     split(root, x, y, v - 1);     cout << si + 1;     merge(root, x, y); }

询问第k小

相当于反着问排名

void ask_num(int x, int kth) {     while(lss + 1 != kth)     {         if(lss >= kth) x = lson;         else kth -= (lss + 1), x = rson;     }     cout << va; }

前驱

在(v-1)处分裂->询问a中最大（第size小）->合并

void ask_fr(int v) {     int x = 0, y = 0;     split(root, x, y, v - 1);     ask_num(x, si);     merge(root, x, y); }

后继

与前驱相反

在(v)处分裂->询问b中第一小->合并

void ask_ba(int v) {     int x = 0, y = 0;     split(root, x, y, v);     ask_num(y, 1);     merge(root, x, y); }

时间复杂度

由于它是期望平衡的，所以它的所有操作都在(o(logn))左右。

总代码（以luogu p3369为例）

#include <bits/stdc++.h> #define lson t[x].ls #define rson t[x].rs #define si t[x].size #define ra t[x].ran #define lss t[t[x].ls].size #define rss t[t[x].rs].size #define va t[x].val using namespace std; int root; namespace treap {     int tot;     struct node     {         int val, size, ls, rs, ran;     }t[100001];     inline void newnode(int &x, int val)     {         ++tot;         t[tot].size=1;         t[tot].val=val;         t[tot].ran=rand();         t[tot].ls=t[tot].rs=0;         x=tot;     }     inline void pushup(int x)     {         si = lss + rss + 1;     }     void split(int x, int &l, int &r, int val)     {         if(!x)         {             l = r = 0;             return;         }         if(va <= val) l = x, split(t[x].rs, t[l].rs, r, val);         else r = x, split(t[x].ls, l, t[r].ls, val);         pushup(x);     }     void merge(int &x, int a, int b)     {         if(!a||!b)         {             x = a + b;             return;         }         if(t[a].ran < t[b].ran) x = a, merge(t[x].rs, t[a].rs, b);         else x = b, merge(t[x].ls, a, t[b].ls);         pushup(x);     }     void insert(int val)     {         int x = 0, y = 0, z = 0;         newnode(z, val);         split(root, x, y, val - 1);         merge(x, x, z);         merge(root, x, y);     }     void del(int val)     {         int x = 0, y = 0, z = 0;         split(root, x, y, val);         split(x, x, z, val - 1);         merge(z, t[z].ls, t[z].rs);         merge(x, x, z);         merge(root, x, y);     }     void ask_rank(int v)     {         int x = 0, y = 0;         split(root, x, y, v - 1);         cout << si + 1;         merge(root, x, y);     }     void ask_num(int x, int kth)     {         while(lss + 1 != kth)         {             if(lss >= kth) x = lson;             else kth -= (lss + 1), x = rson;         }         cout << va;     }     void ask_fr(int v)     {         int x = 0, y = 0;         split(root, x, y, v - 1);         ask_num(x, si);         merge(root, x, y);     }     void ask_ba(int v)     {         int x = 0, y = 0;         split(root, x, y, v);         ask_num(y, 1);         merge(root, x, y);     } }; using namespace treap; int main() {     int n;     cin >> n;     srand(2005);     while(n--)     {         int x, y;         cin >> x >> y;         if(x == 1) insert(y);         else if(x == 2) del(y);         else if(x == 3) ask_rank(y), cout << endl;         else if(x == 4) ask_num(root, y), cout << endl;         else if(x == 5) ask_fr(y), cout << endl;         else if(x == 6) ask_ba(y), cout << endl;     }     return 0; }

完结，撒花！！！！！！！★,°:.☆(￣▽￣)/$:.°★ 。