浅谈非旋Treap
zhouwc
2018-10-02 13:28:28
#### 放入我的[博客](http://zwcblog.top./4ccf99cf81c42233c714e9064d32a457/2018/07/21/c%E5%AD%A6%E4%B9%A0%E7%AC%94%E8%AE%B0%EF%BC%9A%E6%8C%87%E9%92%88/)食用效果更佳（有很多oi学习资料）
### 概述
本文按个人的理解讲述，可能有错误。
普通的二叉搜索树用途很广但容易退化，在许多情况下时间复杂度不是很理想，所以诞生了很多基于二叉搜索树并尽量使其趋向于平衡的数据结构：AVL树，红黑树，2-3树等等。本文来讨论一种相对来讲比较奇葩的数据结构：Treap。Treap=Tree+Heap，它是通过随机化的方式来使树在期望情况下不会有太大的高度。Treap代码简单，期望情况下有不错的效率，且非旋Treap适用范围广，非常适合信息学竞赛。
### 基本性质
一般的Treap中每一个节点有两个属性：key（键值），rank（秩）。要求键值维持搜索树的性质，秩维护小根堆的性质。即根的键值大于等于其左子树所有节点的键值，且小于等于其右子树所有结点的键值，根的秩小于等于其儿子的秩。我们在新产生节点的时候赋予节点一个随机的秩以便使Treap趋向于平衡。
Treap的期望树高为$O(lgn)$下面给出一个不是特别严谨的证法：
之所以说不严谨，是因为这个证法需要基于两条假设：结点的秩两两不同且完全随机，键值两两不同。
【引理1】在所有节点的秩和键值被确定后，Treap的形态是唯一的。
证：对Treap中的结点个数进行归纳证明。
当Treap中只有一个结点或没有结点时形态是唯一的，易得。
当Treap中结点个数大于1时，基于我们的假设，结点的秩两两不同，所以秩最小的结点一定是Treap的根。那么根结点的键值被确定了，则其左子树有哪些结点，右子树有哪些结点也被确定了。基于归纳法，左子树和右子树的形态是唯一的，所以该Treap的形态是唯一的。
证毕。
我们定义一棵Treap的界为其$2^{树高}$（这里树高从0开始）（特别地，当Treap中没有元素时界为0）。
【引理2】一棵有n个结点的Treap期望界为$O(n^3)$。
证：对Treap中的结点个数进行归纳证明。
设f(n)为一棵n个结点的Treap的期望界，我们用归纳法证明$f(n)\le n^3$。
易得，f(0)=0,f(1)=1。
当n>1时，由于秩完全随机，所以根是完全随机的，因此可得
$f(n)=\frac{1}{n}\displaystyle\sum_{i=0}^{n-1}(2max(f(i),f(n-1-i)))$
$\le \frac{4}{n}\displaystyle\sum_{i=0}^{n-1}f(i)$
$\le \frac{4}{n}\displaystyle\sum_{i=0}^{n-1}i^3$
$= \frac{4}{n}\times \frac{n^2(n-1)^2}{4} $
$\le n^3 $
证毕。
【推论1】一棵Treap的期望树高为$O(lgn)$。
证明：由于Treap的期望界为O(n^3)，所以由琴生不等式得Treap的期望树高为O(lgn)。
证毕。
### 非旋Treap的操作
#### 概述
Treap按实现来说可以分两种：旋转型和非旋转型，旋转型主要是通过旋转来维护Treap的性质的，而非旋转型是通过拆裂和合并来实现操作的。个人认为非旋Treap有着更广的适用范围且代码更好写。
#### 合并与拆裂
非旋Treap的两个关键的操作是拆裂和合并：
合并函数：int merge(int x,int y)该函数传入两个需要合并的Treap的根（要保证左边的Treap中的所有元素小于等于右边的），然后返回合并后的根。这个函数可以使用类似于左偏树合并的方法递归来写。（up函数是用于更新结点信息的，后面同理）取秩小的作为根，然后另一棵Treap和根的对应子树合并。
```cpp
int merge(int x,int y){
if(x*y==0) return x+y; //如果有一个为空返回另一个
if(tree[x].rank<tree[y].rank) {
tree[x].son[1]=merge(tree[x].son[1],y);
up(x); return x;
}else{
tree[y].son[0]=merge(x,tree[y].son[0]);
up(y); return y;
}
}
```
拆裂函数：pair<int,int> split(int x,int sz)该函数传入当前处于的结点位置和需要拆成两部分中第一部分的大小，返回拆成的两个根。同样可以使用递归的方法来写。对拆的位置分类，分别求解。
```cpp
pair<int,int> split(int x,int sz){
if(x==0) return make_pair(0,0);
int ksz=tree[tree[x].son[0]].sz+1;
if(sz==ksz){
int y=tree[x].son[1];
tree[x].son[1]=0,up(x);
return make_pair(x,y);
}
if(sz<ksz){
pair<int,int> y=split(tree[x].son[0],sz);
tree[x].son[0]=y.second,up(x);
return make_pair(y.first,x);
}else{
pair<int,int> y=split(tree[x].son[1],sz-ksz);
tree[x].son[1]=y.first,up(x);
return make_pair(x,y.second);
}
}
```
#### 插入与删除
我们可以再写一个函数int get(int key)用于计算该Treap中有多少个元素比key小（sz表示该结点对应子树中的结点个数）。代码比较简单：
```cpp
int get(int key){
int x=root,ret=0;
while(x!=0){
int t=key>tree[x].key;
if(t==1) ret+=tree[tree[x].son[0]].sz+1;
x=tree[x].son[t];
}
return ret;
}
```
再写一个函数int new_node(int sz,int key)用于新建结点。
```cpp
struct Node{
int son[2],key,sz,rank;
};
static Node tree[MAX_N];
static int top; //表示开了多少个节点
static int new_node(int sz,int key){
tree[++top]=(Node){{0,0},key,sz,(rand()<<16)+rand()}; //自然溢出增加随机性
return top; //如果无用内存过多可以选择用栈。
}
```
有了这些函数，插入删除就变得很简单了。
插入的话只需要用get函数找出对应位置然后拆开来，新建结点后依次将三个根合并就行了（由于我的拆裂和合并函数考虑了传入值为空的情况所以不需要特判）。
```cpp
void insert(int key){
int sz=get(key);
pair<int,int> y=split(root,sz);
root=merge(y.first,merge(new_node(1,key),y.second));
}
```
同理，删除是拆成三份然后合并其中的两份。
```cpp
void erase(int key){
int sz=get(key);
pair<int,int> y=split(root,sz);
root=merge(y.first,split(y.second,1).second);
}
```
#### 其它操作
其它什么前驱后继，找第几个元素是什么都随便搞一下就好了，找道板子题普通平衡树A一下：
```cpp
#include<cstdio>
#include<algorithm>
#include<cstdlib>
using namespace std;
const int MAX_N=5+1e5;
class Treap{
public:
struct Node{
int son[2],key,sz,rank;
};
static Node tree[MAX_N];
static int top;
int root;
static int new_node(int sz,int key){
tree[++top]=(Node){{0,0},key,sz,(rand()<<16)+rand()};
return top;
}
void up(int x){
tree[x].sz=tree[tree[x].son[0]].sz+tree[tree[x].son[1]].sz+1;
}
Treap(){ root=0; }
int get(int key){
int x=root,ret=0;
while(x!=0){
int t=key>tree[x].key;
if(t==1) ret+=tree[tree[x].son[0]].sz+1;
x=tree[x].son[t];
}
return ret;
}
int find(int sz){
int x=root,ksz;
while((ksz=tree[tree[x].son[0]].sz+1)!=sz){
if(sz>ksz) sz-=ksz,x=tree[x].son[1];
else x=tree[x].son[0];
}
return x;
}
int merge(int x,int y){
if(x*y==0) return x+y;
if(tree[x].rank<tree[y].rank) {
tree[x].son[1]=merge(tree[x].son[1],y);
up(x); return x;
}else{
tree[y].son[0]=merge(x,tree[y].son[0]);
up(y); return y;
}
}
pair<int,int> split(int x,int sz){
if(x==0) return make_pair(0,0);
int ksz=tree[tree[x].son[0]].sz+1;
if(sz==ksz){
int y=tree[x].son[1];
tree[x].son[1]=0,up(x);
return make_pair(x,y);
}
if(sz<ksz){
pair<int,int> y=split(tree[x].son[0],sz);
tree[x].son[0]=y.second,up(x);
return make_pair(y.first,x);
}else{
pair<int,int> y=split(tree[x].son[1],sz-ksz);
tree[x].son[1]=y.first,up(x);
return make_pair(x,y.second);
}
}
void insert(int key){
int sz=get(key);
pair<int,int> y=split(root,sz);
root=merge(y.first,merge(new_node(1,key),y.second));
}
void erase(int key){
int sz=get(key);
pair<int,int> y=split(root,sz);
root=merge(y.first,split(y.second,1).second);
}
int to_key(int x){ return tree[x].key; }
int prev(int key){ return to_key(find(get(key))); }
int succ(int key){ return to_key(find(get(key+1)+1)); }
}treap;
Treap::Node Treap::tree[MAX_N];
int Treap::top=-1;
int main(){
srand(998244353); //注意不要用time(NULL)，正式比赛中会RE。
Treap::new_node(0,0);
int n; scanf("%d",&n);
while(n--){
int opt; scanf("%d",&opt);
switch(opt){
case 1:{
int key; scanf("%d",&key);
treap.insert(key);
break;
}
case 2:{
int key; scanf("%d",&key);
treap.erase(key);
break;
}
case 3:{
int key; scanf("%d",&key);
printf("%d\n",treap.get(key)+1);
break;
}
case 4:{
int x; scanf("%d",&x);
printf("%d\n",treap.to_key(treap.find(x)));
break;
}
case 5:{
int key; scanf("%d",&key);
printf("%d\n",treap.prev(key));
break;
}
case 6:{
int key; scanf("%d",&key);
printf("%d\n",treap.succ(key));
break;
}
}
}
return 0;
}
```
这个代码易写易调试，熟练了可以15分钟码一棵非旋Treap。
#### 操作的时间复杂度
这些操作都是O(树高)的，而我们前面已经证明了树高为期望O(lgn)，所以Treap实现这些操作的期望时间复杂度均为O(lgn)。
### 数列Treap
#### 概述
我们知道伸展树可以用于维护序列上的内容（如区间加，查询区间和，插入值等等），Treap同样可以，而非旋Treap拆裂合并的方式可以使维护数列变得更加简单，而且非旋Treap能在期望O（lgn）的期望时间内实现区间翻转等其他数据结构难以实现的操作。
#### 一些代码上的更改
用于维护数列的Treap不需要get函数，因为其本身就是以元素在数列中的位置为线索的。与SplayTree类似，我们同样使用懒惰标记的方式来维护，我们写一个up函数和一个down函数，只需要用它们在merge和split时下放和维护节点信息即可。我找了【POJ3580】SuperMemo切了一下，可以看下我代码：
```cpp
#include<cstdio>
#include<algorithm>
using namespace std;
const int MAX_N=5+2e5;
class Treap{
struct Node{
int son[2],sz,key,rank,min;
int tag1; bool tag2;
}tree[MAX_N];
int top,root;
int _rand(){
static int seed=1e9+7;
return seed=seed*31+998244353;
}
int new_node(int sz,int key){
tree[++top]=(Node){{0,0},sz,key,_rand(),key,0,false};
return top;
}
void put_tag(int x,int tag1,bool tag2){
if(!x) return;
if(tag2){
swap(tree[x].son[0],tree[x].son[1]);
tree[x].tag2^=1;
}
tree[x].min+=tag1;
tree[x].key+=tag1;
tree[x].tag1+=tag1;
}
void down(int x){
put_tag(tree[x].son[0],tree[x].tag1,tree[x].tag2);
put_tag(tree[x].son[1],tree[x].tag1,tree[x].tag2);
tree[x].tag1=0,tree[x].tag2=false;
}
void up(int x){
tree[x].min=min(tree[x].key,min(tree[tree[x].son[0]].min
,tree[tree[x].son[1]].min));
tree[x].sz=tree[tree[x].son[0]].sz+tree[tree[x].son[1]].sz+1;
}
public:
void clear(){ top=-1,new_node(0,2e9); }
int merge(int x,int y){
if(x==0) return y;
if(y==0) return x;
if(tree[x].rank<tree[y].rank){
down(x),tree[x].son[1]=merge(tree[x].son[1],y);
up(x); return x;
}else{
down(y),tree[y].son[0]=merge(x,tree[y].son[0]);
up(y); return y;
}
}
pair<int,int> split(int x,int sz){
if(x==0) return make_pair(0,0);
down(x);
int ksz=tree[tree[x].son[0]].sz+1;
if(sz==ksz){
int y=tree[x].son[1];
tree[x].son[1]=0,up(x);
return make_pair(x,y);
}
if(sz<ksz){
pair<int,int> y=split(tree[x].son[0],sz);
tree[x].son[0]=y.second,up(x);
return make_pair(y.first,x);
}else{
pair<int,int> y=split(tree[x].son[1],sz-ksz);
tree[x].son[1]=y.first,up(x);
return make_pair(x,y.second);
}
}
void insert(int sz,int key){
pair<int,int> y=split(root,sz);
root=merge(y.first,merge(new_node(1,key),y.second));
}
void erase(int sz){
pair<int,int> y=split(root,sz-1);
root=merge(y.first,split(y.second,1).second);
}
void change(int l,int r,int tag1,bool tag2){
pair<int,int> y=split(root,r);
pair<int,int> z=split(y.first,l-1);
put_tag(z.second,tag1,tag2);
root=merge(merge(z.first,z.second),y.second);
}
int query(int l,int r){
pair<int,int> y=split(root,r);
pair<int,int> z=split(y.first,l-1);
int ret=tree[z.second].min;
root=merge(merge(z.first,z.second),y.second);
return ret;
}
void revolve(int l,int r,int t){
t=(t%(r-l+1)+r-l+1)%(r-l+1);
pair<int,int> y=split(root,r-t);
pair<int,int> a=split(y.first,l-1);
pair<int,int> b=split(y.second,t);
root=merge(merge(a.first,b.first),merge(a.second,b.second));
}
}treap;
char s[60];
int main(){
int n;
while(scanf("%d",&n)!=-1){
treap.clear();
for(int i=1;i<=n;++i){
int key; scanf("%d",&key);
treap.insert(i,key);
}
int m; scanf("%d",&m);
while(m--){
scanf("%s",s+1);
if(s[1]=='A'){
int l,r,key; scanf("%d%d%d",&l,&r,&key);
if(l>r) swap(l,r);
treap.change(l,r,key,false);
}else if(s[1]=='R'&&s[4]=='E'){
int l,r; scanf("%d%d",&l,&r);
if(l>r) swap(l,r);
treap.change(l,r,0,true);
}else if(s[1]=='R'&&s[4]=='O'){
int l,r,t; scanf("%d%d%d",&l,&r,&t);
if(l>r) swap(l,r);
treap.revolve(l,r,t);
}else if(s[1]=='I'){
int x,key; scanf("%d%d",&x,&key);
treap.insert(x,key);
}else if(s[1]=='D'){
int x; scanf("%d",&x);
treap.erase(x);
}else {
int l,r; scanf("%d%d",&l,&r);
if(l>r) swap(l,r);
printf("%d\n",treap.query(l,r));
}
}
}
return 0;
}
```
版权声明：此篇文章为本博客管理员“傻逼”所写