关于非旋转Treap
2020-01-09 16:01:04来源:博客园 阅读 ()
关于非旋转Treap
刚刚跟着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;
}
完结,撒花!!!!!!!★,°:.☆( ̄▽ ̄)/$:.°★ 。
原文链接:https://www.cnblogs.com/H2SO4/p/12170467.html
如有疑问请与原作者联系
标签:
版权申明:本站文章部分自网络,如有侵权,请联系:west999com@outlook.com
特别注意:本站所有转载文章言论不代表本站观点,本站所提供的摄影照片,插画,设计作品,如需使用,请与原作者联系,版权归原作者所有
- 关于各种不同开发语言之间数据加密方法(DES,RSA等)的互通的 2020-06-07
- 关于使用ffmpeg的一些牢骚 2020-05-08
- 关于有趣的windows.h 2020-03-09
- 关于C/C++的各种优化 2020-02-06
- 关于C/C++的各种优化 2020-01-20
IDC资讯: 主机资讯 注册资讯 托管资讯 vps资讯 网站建设
网站运营: 建站经验 策划盈利 搜索优化 网站推广 免费资源
网络编程: Asp.Net编程 Asp编程 Php编程 Xml编程 Access Mssql Mysql 其它
服务器技术: Web服务器 Ftp服务器 Mail服务器 Dns服务器 安全防护
软件技巧: 其它软件 Word Excel Powerpoint Ghost Vista QQ空间 QQ FlashGet 迅雷
网页制作: FrontPages Dreamweaver Javascript css photoshop fireworks Flash