Treap
upd on 2020/1/28
旋转Treap
·什么是BST？
Binary Search Tree 二叉搜索树
性质：
根节点的值大于左子树的值，小于右子树的值。
好处：
1.搜索作用
寻找k，如果比根大，在右子树，否则在左子树。
2.划分（同1）
3.同样的N的数字，由于插入BST的顺序不同，会导致树的形态不同。
·旋转平衡树（Splay会用）
旋转
例子：
·非旋转平衡树（FHQ-Treap）
什么是Treap
众所周知，Treap = tree + heap
1.heap（堆）
嗯？堆不是可以用priority_queue吗？
但是在Treap里，我们只能手工实现堆QWQ
对于堆来说，他是一个完全二叉树。
大/小根堆：根节点大/小于左右子树节点值
代码。。木有
1.5.为毛要用heap？
完全二叉树啊喂！！！
深度最低啊喂！！！
然鹅。。。
BST和heap在树的形态上是冲突的。
☞怎么解决？
Treap必须是一棵BST，heap只是一种辅助。
∴我们可以随机给每个节点一个值，用作heap。
那每个节点要有什么值呢？
（1）左儿子、右儿子
（2）爸爸
（3）子树节点数
（4）自己的值
（5）随机值
例题
loj #104 普通平衡树
然后。。。你可以再交一次P3369
非旋Treap
1.非旋Treap是什么？
又称fhq-Treap，非旋转，操作多，常数小。
有两种操作。
2.split（分裂）& merge（合并）
实际上，学习FHQTreap，你只需要会这两个操作就行了
split：将一个BST分成两个BST
（1）按value值分裂（分成两棵树，其中一棵上的节点都小于等于k）
（2）按sz值分裂（分成两棵树，其中一颗sz值为k）
merge：将两个BST合成一个BST
例题：loj #105 文艺平衡树 loj #104 普通平衡树
然后。。。你可以再交一次P3391
代码码：（P3369）
#include<iostream>
#include<ctime>
#include<cstdlib>
using namespace std;
int n,root;
int siz[100010],num[100010],rnd[100010];
int x,y,z;
int cnt;
struct Node
{
int l,r;
}s[100010];
void upd(int a)
{
siz[a] = siz[s[a].l] + siz[s[a].r] + 1;
}
void split(int now,int k,int &x,int &y)
{
if (!now)
{
x = y = 0;
}
else if (num[now] <= k)
{
x = now;
split(s[now].r,k,s[now].r,y);
upd(now);
}
else
{
y = now;
split(s[now].l,k,x,s[now].l);
upd(now);
}
}//分裂函数
int merge(int ta,int tb)
{
if (!ta && !tb) return 0;
if (!tb) return ta;
if (!ta) return tb;
if (rnd[ta] < rnd[tb])
{
s[ta].r = merge(s[ta].r,tb);
upd(ta);
return ta;
}
else
{
s[tb].l = merge(ta,s[tb].l);
upd(tb);
return tb;
}
}//合并函数
void ins(int a)
{
split(root,a,x,y);//split可以是原树保持平衡
siz[++cnt] = 1;
num[cnt] = a;
rnd[cnt] = rand();
root = merge(merge(x,cnt),y);
}//新增节点函数
void del(int a)
{
split(root,a,x,z);
split(x,a - 1,x,y);
//这里注意一个问题，我们并没有算重复数字在一个节点里，所以sz[y] > 1
root = merge(merge(x,merge(s[y].l,s[y].r)),z);
}//删除节点函数
void rnk(int a)
{
//这个函数的本质是分裂出一棵所有节点都 <= a的一棵树，那么这棵树的大小+1就是a的排名
split(root,a - 1,x,y);
cout << siz[x] + 1 << endl;
root = merge(x,y);
}//查询排名函数
int fnd(int a,int now)
{
//从root开始，若a <= now左子树的sz，则进入左子树；否则进入右子树，且把查询的a减去左子树的sz再减1
while (1)
{
if (siz[s[now].l] >= a) now = s[now].l;
else if (siz[s[now].l] + 1 == a)
{
return now;
}
else
{
a -= siz[s[now].l] + 1;
now = s[now].r;
}
}
}//由排名找节点函数
void frnt(int a)
{
//分裂出value <= a - 1的一棵树，这棵树的根（第x名）即为a的前驱
split(root,a - 1,x,y);
//cout << fnd(siz[x],x) << endl;
cout << num[fnd(siz[x],x)] << endl;
root = merge(x,y);
}//找前驱函数
void bck(int a)
{
//分裂出value > a的一棵树，这棵树的根（第一名）即为a的后继
split(root,a,x,y);
cout << num[fnd(1,y)] << endl;
root = merge(x,y);
}//找后继函数
int main()
{
srand((unsigned)time(NULL));
cin >> n;
for (int i = 1;i <= n;i ++)
{
int opt,a;
cin >> opt >> a;
if (opt == 1)
{
ins(a);
}
else if (opt == 2)
{
del(a);
}
else if (opt == 3)
{
rnk(a);
}
else if (opt == 4)
{
cout << num[fnd(a,root)] << endl;
}
else if (opt == 5)
{
frnt(a);
}
else if (opt == 6)
{
bck(a);
}
}
}具体思路见下面的那个博客（吹爆）
好的博客：Chanis/fhq-treap
upd on 2020/1/29
文艺平衡树
题目
首先，为什么区间翻转能用FHQ-Treap捏？
For instance,
翻转1-3，我们可以分裂出一颗子树（u），其sz == 3
之后直接翻转这棵树，就可以了
怎么翻转呢？
首先，我们知道从小到大是中序遍历
那么从大到小呢？
其实很简单，右中左就行了
我们可以打一个标记（fl），代表他翻转了
可是，如果对一棵被包含的子树（v）翻转呢？
标记下传！
代码可参考：Chanis/fhq-treap
未完待续。。。
（同步发表于CSDN博客RabbieWjy）