Treap小结

本文主要是介绍Treap小结，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

Treap(Tree+Heap)---是一种通过 rand() 来随机生成数字作为修正值来调整的平衡树。

基本操作：

1.旋转。

2.插入（合并重复的），删除（懒惰删除）。

3.查最值，求第k小，求排名。

4.中序遍历就是从小到大的。

5.维护附加关键字.

1.求第k小:

POJ1442

//12321199		1442	Accepted	976K	204MS	C++	2080B	2013-11-22 20:33:35静态
//12321216		1442	Accepted	1804K	329MS	C++	2125B	2013-11-22 20:39:40动态
#include <iostream>
#include<cstdio>
#include<ctime>
#include<cstring>
#include<cstdlib>
using namespace std;
#define MAX 30005
int a[MAX];
int u[MAX];
int tot;
class Node
{
public:int vol,fix;int size;Node *left;Node *right;int lsize(){return left?left->size:0;}int rsize(){return right?right->size:0;}
}*root;//space[MAX]
void left_rotate(Node *&a)
{Node *b=a->right;a->right=b->left;b->left=a;a=b;b=a->left;b->size=b->lsize()+b->rsize()+1;a->size=a->lsize()+a->rsize()+1;
}
void right_rotate(Node *&a)
{Node *b=a->left;a->left=b->right;b->right=a;a=b;b=a->right;b->size=b->lsize()+b->rsize()+1;a->size=a->lsize()+a->rsize()+1;
}
void insert(Node*&p,int vol)
{if(!p){p=new Node();//p=&space[tot++];  //静态p->fix=rand();p->vol=vol;p->size=1;}else if(vol<=p->vol){insert(p->left,vol);p->size++;if(p->left->fix < p->fix)right_rotate(p);}else{insert(p->right,vol);p->size++;if(p->right->fix < p->fix)left_rotate(p);}
}
int get_kth(Node *&p,int k)
{int key=p->lsize()+1;if(k < key)return get_kth(p->left,k);else if(k > key)return get_kth(p->right,k-key);elsereturn p->vol;
}
void init()
{root=NULL;//memset(space,0,sizeof(space));静态//tot=1;
}
int main()
{srand(time(0));int n,m;while(~scanf("%d%d",&m,&n)){for(int i=1;i<=m;i++) scanf("%d",&a[i]);for(int i=1;i<=n;i++) scanf("%d",&u[i]);int j=1;init();for(int i=1;i<=m;i++){insert(root,a[i]);while(j<=n&&i==u[j]){printf("%d\n",get_kth(root,j));j++;}if(j>n) break;}}return 0;
}

2.动态求最值

//12321728		3481	Accepted	212K	282MS	C++	1857B	2013-11-22 22:26:19动态
#include <iostream>
#include<cstdlib>
#include<ctime>
#include<cstdio>
#include<cstring>
using namespace std;
//#define MAX 10000005
class Node
{
public:int vol,fix,cus;Node* left;Node* right;
}*root;//,space[MAX]  
int tot=1;
void r_rotate(Node*&a)
{Node*b=a->left;a->left=b->right;b->right=a;a=b;b=a->right;
}
void l_rotate(Node*&a)
{Node*b=a->right;a->right=b->left;b->left=a;a=b;b=a->left;
}
void insert(Node*&p,int cus,int vol)
{if(!p){p=new Node();//p=&space[tot++];p->fix=rand();p->vol=vol;p->cus=cus;}else if(p->vol >= vol){insert(p->left,cus,vol);if(p->left->fix < p->fix)r_rotate(p);}else{insert(p->right,cus,vol);if(p->right->fix < p->fix)l_rotate(p);}
}
int Min(Node*&p)
{if(!p)return 0;if(!p->left){Node*t=p;int ans=p->cus;p=p->right;delete t;return ans;}else return Min(p->left);
}
int Max(Node*&p)
{if(!p)return 0;if(!p->right){Node*t=p;int ans=p->cus;p=p->left;delete t;return ans;}else return Max(p->right);
}
int main()
{srand(time(0));int a;while(~scanf("%d",&a)&&a){if(a==1){int b,c;scanf("%d%d",&b,&c);insert(root,b,c);}else if(a==3){printf("%d\n",Min(root));}else{printf("%d\n",Max(root));}}return 0;
}

3.区间第k小:

//12329808		2761	Accepted	3500K	1844MS	C++	3889B	2013-11-25 21:28:45静态
//12329836		2761	Accepted	3900K	3922MS	C++	3962B	2013-11-25 21:34:10动态
#include <iostream>
#include<cstdio>
#include<ctime>
#include<cstdlib>
#include<cstring>
#include<algorithm>
using namespace std;
#define MAX 2000005
int dog[MAX];
int ans[MAX];
class Interval
{
public:int s,e,k;int id;bool operator<(const Interval a) const{return s<a.s;}
}qu[MAX];
class Node
{
public:int vol,fix,size;Node*left;Node*right;int lsize(){return left?left->size:0;}int rsize(){return right?right->size:0;}
}*root,space[MAX];
int tot;
void r_rotate(Node*&a)
{Node*b=a->left;a->left=b->right;b->right=a;a=b;b=a->right;b->size=b->lsize()+b->rsize()+1;/**RE在这里，不要把求size顺序搞反了*/a->size=a->lsize()+a->rsize()+1;}
void l_rotate(Node*&a)
{Node*b=a->right;a->right=b->left;b->left=a;a=b;b=a->left;b->size=b->lsize()+b->rsize()+1;a->size=a->lsize()+a->rsize()+1;}
void insert(Node*&p,int vol)
{if(!p){p=&space[tot++];//p=new Node();p->left=NULL;p->right=NULL;p->fix=rand();p->vol=vol;p->size=1;}else if(p->vol > vol){p->size++;insert(p->left,vol);if(p->left->fix < p->fix)r_rotate(p);}else{p->size++;insert(p->right,vol);if(p->right->fix < p->fix)l_rotate(p);}
}
void del(Node*&p,int key)
{if(!p) return ;p->size--;  /**注意size的减减**/if(key==p->vol){if(!p->left || !p->right){//Node *t=p;if(!p->left)p=p->right;elsep=p->left;//delete t;}else{if(p->right->fix < p->left->fix){l_rotate(p);p->size--;/**注意size的减减**/del(p->left,key);}else{r_rotate(p);p->size--;/**注意size的减减**/del(p->right,key);}}}else if(key < p->vol)del(p->left,key);elsedel(p->right,key);
}
int find_kth(Node*&p,int k)
{int sum=p->lsize()+1;if(k < sum){return find_kth(p->left,k);}else if(k>sum){return find_kth(p->right,k-sum);}else{return p->vol;}
}
int solve(Interval t1,Interval t2)
{for(int i=t1.s;i<=min(t2.s-1,t1.e);i++)del(root,dog[i]);if(t1.e > t2.e){for(int i=t2.e+1;i<=t1.e;i++)del(root,dog[i]);}for(int i=max(t1.e+1,t2.s);i<=t2.e;i++)insert(root,dog[i]);return find_kth(root,t2.k);
}
int main()
{srand(time(0));//int T;//scanf("%d",&T);int n,m;while(~scanf("%d%d",&n,&m)){root=NULL;tot=1;memset(space,NULL,sizeof(space));for(int i=1;i<=n;i++)scanf("%d",&dog[i]);for(int i=1;i<=m;i++){scanf("%d%d%d",&qu[i].s,&qu[i].e,&qu[i].k);if(qu[i].s > qu[i].e) swap(qu[i].s,qu[i].e);qu[i].id=i;}sort(qu+1,qu+1+m);for(int i=qu[1].s;i<=qu[1].e;i++)insert(root,dog[i]);ans[qu[1].id]=find_kth(root,qu[1].k);for(int i=2;i<=m;i++){ans[qu[i].id]=solve(qu[i-1],qu[i]);}for(int i=1;i<=m;i++)printf("%d\n",ans[i]);}return 0;
}

这篇关于Treap小结的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---