首页 > 代码库 > treap完全版模板
treap完全版模板
这是我综合poj1442 3481 2352的treap操作 得到treap完全版模板。（经测AC）
从NOCOW——Treap中一份代码中模仿加工精致而成。
结构体Tree
{
int key; //键值
int size; //该子树总节点个数
int pri; //其随机值
int son[2]; //从nocow一份代码中学来的，0表示左儿子，1表示右儿子，旋转只需一个函数即可
(int num;) //该节点在序列中的原位置，可添加
}
该Treap模板支持操作：
1. 插入值
2. 删除值
3. 找出第p小的节点的编号（找最大只需find(T[rt].size, rt);）
4. 找出值小于等于key的节点个数
（添加其他类似操作均可自己修改）
#include <cstdio>#include <cstring>#include <ctime>#include <iostream>#include <algorithm>#include <cstdlib>#include <cmath>#include <utility>#include <vector>#include <queue>#include <map>#include <set>#define max(x,y) ((x)>(y)?(x):(y))#define min(x,y) ((x)>(y)?(y):(x))#define INF 0x3f3f3f3f#define MAXN 100005using namespace std;int cnt=1,rt=0; //节点编号从1开始struct Tree{ int key, size, pri, son[2]; //保证父亲的pri大于儿子的pri void set(int x, int y, int z) { key=x; pri=y; size=z; son[0]=son[1]=0; }}T[MAXN];void rotate(int p, int &x){ int y=T[x].son[!p]; T[x].size=T[x].size-T[y].size+T[T[y].son[p]].size; T[x].son[!p]=T[y].son[p]; T[y].size=T[y].size-T[T[y].son[p]].size+T[x].size; T[y].son[p]=x; x=y;}void ins(int key, int &x){ if(x == 0) T[x = cnt++].set(key, rand(), 1); else { T[x].size++; int p=key < T[x].key; ins(key, T[x].son[!p]); if(T[x].pri < T[T[x].son[!p]].pri) rotate(p, x); }}void del(int key, int &x) //删除值为key的节点{ if(T[x].key == key) { if(T[x].son[0] && T[x].son[1]) { int p=T[T[x].son[0]].pri > T[T[x].son[1]].pri; rotate(p, x); del(key, T[x].son[p]); } else { if(!T[x].son[0]) x=T[x].son[1]; else x=T[x].son[0]; } } else { T[x].size--; int p=T[x].key > key; del(key, T[x].son[!p]); }}int find(int p, int &x) //找出第p小的节点的编号{ if(p == T[T[x].son[0]].size+1) return x; if(p > T[T[x].son[0]].size+1) find(p-T[T[x].son[0]].size-1, T[x].son[1]); else find(p, T[x].son[0]);}int find_NoLarger(int key, int &x) //找出值小于等于key的节点个数{ if(x == 0) return 0; if(T[x].key <= key) return T[T[x].son[0]].size+1+find_NoLarger(key, T[x].son[1]); else return find_NoLarger(key, T[x].son[0]); }
treap完全版模板
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。