剛剛跟著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.uj5u.com/houduan/73332.html
標籤：C++
下一篇：面向程序和面向物件