关键词：
非旋Treap
->模板地址
（为便于理解，以下演示代码均使用数组版）
概述
非旋Treap是一种按照堆的原理以随机权值来维护平衡树平衡的平衡树，在一般情况下，非旋Treap趋于平衡，但不稳定。非旋Treap的基本操作少，实现简单，作用范围广，基本可以实现Splay所支持的操作
（节点压缩的Treap请跳转，此篇博客为基本操作和使用）
（此博客不包含可持久化Treap，可持久化请跳转）
平衡树的定义
由四个部分组成：左右儿子、节点大小、随机权值、节点数值，其中节点数值为任意类型
struct node
int son[2];//左右儿子
int s,v;//节点大小和随机权值
int c;//节点数值
node()
son[0] = son[1] = 0;
s = 0;
v = rand();//给节点附随机权值
t[100001];
void push_up(int p) //更新节点信息
t[p].s = t[p * 2].s + t[p * 2 + 1].s + 1;
基本操作
注意访问到空节点是要立即返回，否则可能回使空节点的size不为0导致各种错误
分裂（split）
将一棵Treap按照一定的要求分裂成两课平衡树，常用的有数值分裂和排名分裂
分裂操作因为每次只需要递归一个子树，所以复杂度平均是树高（log(n)）的
数值分裂
把数值小于等于给定数值的节点置于一棵平衡树中，其它的置于另一棵平衡树中
为方便表述，我们将放置数值小于等于给定数值的节点的平衡树称为左侧平衡树，另一棵称为右侧平衡树
从给定的根节点开始，若当前节点的数值大于给定数值，将其及其右子树置于右侧平衡树，继续分裂左子树，反之将其及其左子树置于左侧平衡树继续分裂右子树
//p为当前节点，v为给定数值，x为分裂后的左侧平衡树的根节点，y为分裂后的右侧平衡树的根节点
void split_v(int p, int v, int &x, int &y)
if(!p)return void(x = y = 0);//分裂到空节点
if(t[p].c <= v)
x = p;//置于左侧平衡树
split_v(t[p].son[1], v, t[p].son[1], y);//分裂右子树
else
y = p;//置于右侧平衡树
split_v(t[p].son[0], v, x, t[p].son[0]);//分裂右子树
push_up(p);
//示例
/*
//root 1,2,3,4,5,6
split_v(root, 3, r1, r2)
//r1 1,2,3
//r2 4,5,6
*/注：引用的使用（不能理解引用的看这里）
x和y均使用引用，这样能使x、y在函数中被赋值，能简化大量代码（不用记录父节点）
对于引用的x和y会在函数中被赋值，附的值分别为子树的根的编号，而一个节点的子节点是子树的根节点，所以可以这样使用（实在不能理解多就打几遍或手推一下）
排名分裂
把前k个节点分在一起，原理同数值分裂（代码复制一下再修改一点即可）
void split_k(int p, int k, int &x, int &y)
if(!p)return void(x = y = 0);
if(k <= t[t[p].son[0]].s)
y = p;
split_k(t[p].son[0], k, x, t[p].son[0]);
else
x = p;
split_k(t[p].son[1], k - t[t[p].son[0]].s - 1, t[p].son[1], y);//注意这里
push_up(p);
//示例
/*
//root 1,3,5,7,9,11
split_k(root, 3, r1, r2)
//r1 1,3,5
//r2 7,9,11
*/合并（merge）
维护平衡树平衡的操作就在这里，原理就是把权值大（小）的作为权值小（大）的节点的父节点，这样就能满足堆的性质
这里的合并不是指的将两个毫不相关的平衡树合并在一起，只是将一棵平衡树接在另一棵后面（如一棵中序遍历为[1,3,5]的Treap和一棵中序遍历为[2,4,6]的平衡树合并后中序遍历为[1,3,5,2,4,5]而不是[1,2,3,4,5,6]）
合并操作因为每次最多需要递归一个子树，所以复杂度平均是树高（log(n)）的
//将x与y合并，返回合并后的根节点
int merge(int x, int y)
if(! x || ! y)return x + y;//一个节点为0则返回不为0的节点
if(t[x].val < t[y].val)
//将x作为父节点，合并x的右子树和y
t[x].son[1] = merge(t[x].son[1], y);
push_up(x);
return x;
else
//将y作为父节点，合并y的左子树和x
t[y].son[0] = merge(x, t[y].son[0]);
push_up(y);
return y;
//示例
/*
//r2 1,2,3
//r1 7,8,9
root=merge(r1,r2)
//root 7,8,9,1,2,3
*/常用操作
所有的常用操作都是由基本操作来的，所以上面的模板可以直接用
对于每个操作，我们可以把Treap想象成一个序列，这样能减少思维复杂度
新建一个节点
int tot=0;
int new_node(int v)
t[++tot].c = v;
t[tot].s=1;
return tot;
插入
将需要插入的地方分裂，然后直接合并
//插入一个新节点
void insert(int v, int &r)
int r1;
r.split_v(r, v, r, r1);
r = merge(r, merge(new_node(v), r1));
删除
将要删除的节点单独分裂出来在合并其它节点即可
void remove(int v, int &r)
int r1, r2;
split_v(r, v - 1, r, r1);
split_k(r1, 1, r2, r1);
r = merge(r, r1);
//r2即为被删除的节点查询第k个节点（k小值）
把前k-1个分裂出来，再把右侧平衡树的第1个节点分裂出来
int kth(int k, int r)
int r1, r2, ans;
split_k(r, k - 1, r, r1);
split_k(r1, 1, r1, r2);
ans = t[r2].c;
r = merge(r, merge(r1, r2));
return ans;
前驱、后继
这个很简单，也有很多方法，原理和上面的差不多（跳过）
排名
这个最简单，分裂后直接输出size就行了
int rank(int v, int r)
int r1;
split_v(r, v - 1, r, r1);
int ans = t[r].s;
r = merge(r, r1);
return ans + 1;
区间操作
非旋Treap也支持区间操作，将要操作的区间分离出来即可，注意如果是需要打标记的操作就需要在分裂中对于每个被访问的节点标记下放
int r1, r2;
split_k(root, l - 1, r1, root);
split_k(root, r - 1, root, r2);
/*do something*/
root = merge(r1, merge(root, r2));典例
首先将板子复制过来然后再考虑怎么做（Treap的正确使用方法）
（典例持续补充中）
普通平衡树
您需要写一种数据结构（可参考题目标题），来维护一些数，其中需要提供以下操作：
- 插入x数
- 删除x数(若有多个相同的数，因只删除一个)
- 查询x数的排名(排名定义为比当前数小的数的个数+1。若有多个相同的数，因输出最小的排名)
- 查询排名为x的数
- 求x的前驱(前驱定义为小于x，且最大的数)
- 求x的后继(后继定义为大于x，且最小的数)
#include<bits/stdc++.h>
using namespace std;
inline int gi()
register int x=0,op=1,c;
while(c=getchar(),c<'0'||c>'9')if(c=='-')op=-op;
x=c^48;
while(c=getchar(),c>='0'&&c<='9')x=(x<<3)+(x<<1)+(c^48);
return x*op;
struct node
int son[2];
int val, s;
int v;
node()
son[0] = son[1] = 0;
s = 0;
val = rand();
t[100001];
void push_up(int p)
t[p].s = t[t[p].son[0]].s + t[t[p].son[1]].s + 1;
void split_v(int p, int v, int &x, int &y)
if(!p)return void(x = y = 0);
if(t[p].v>v)
y = p;
split_v(t[p].son[0], v, x, t[p].son[0]);
else
x = p;
split_v(t[p].son[1], v, t[p].son[1], y);
push_up(p);
void split_k(int p, int k, int &x, int &y)
if(!p)return void(x = y = 0);
if(k <= t[t[p].son[0]].s)
y = p;
split_k(t[p].son[0], k, x, t[p].son[0]);
else
x = p;
split_k(t[p].son[1], k - t[t[p].son[0]].s - 1, t[p].son[1], y);
push_up(p);
int merge(int x, int y)
if(! x || ! y)return x + y;
if(t[x].val < t[y].val)
t[x].son[1] = merge(t[x].son[1], y);
push_up(x);
return x;
else
t[y].son[0] = merge(x, t[y].son[0]);
push_up(y);
return y;
int tot=0;
int new_node(int v)
t[++tot].v = v;
t[tot].s=1;
return tot;
int root=0;
int main()
srand(time(0));
int n=gi();
int op,x;
int r1,r2;
while(n--)
op=gi(),x=gi();
switch(op)
case 1://插入
split_v(root,x,root,r1);
root=merge(root,merge(new_node(x),r1));
break;
case 2://删除
split_v(root,x-1,root,r1);
split_k(r1,1,r2,r1);
root=merge(root,r1);
break;
case 3://排名
split_v(root,x-1,root,r1);
printf("%d
",t[root].s+1);
root=merge(root,r1);
break;
case 4://k小值
split_k(root,x-1,root,r1);
split_k(r1,1,r1,r2);
printf("%d
",t[r1].v);
root=merge(root,merge(r1,r2));
break;
case 5://前驱
split_v(root,x-1,root,r1);
split_k(root,t[root].s-1,root,r2);
printf("%d
",t[r2].v);
root=merge(root,merge(r2,r1));
break;
case 6://后继
split_v(root,x,root,r1);
split_k(r1,1,r1,r2);
printf("%d
",t[r1].v);
root=merge(root,merge(r1,r2));
return 0;
非旋treap结构体数组版（无指针）详解，有图有真相(代码片段)
非旋 $treap$（FHQtreap）的简单入门 前置技能建议在掌握普通treap以及左偏堆（也就是可并堆）食用本blog原理以随机数维护平衡，使树高期望为logn级别，FHQ 不依靠旋转，只有两个核心操作merge（合并）和split（拆分）所... 查看详情
非旋treap结构体数组版（无指针）详解，有图有真相(代码片段)
非旋 $treap$（FHQtreap）的简单入门 前置技能建议在掌握普通treap以及左偏堆（也就是可并堆）食用本blog原理以随机数维护平衡，使树高期望为logn级别，FHQ 不依靠旋转，只有两个核心操作merge（合并）和split（拆分）所... 查看详情
非旋treap(代码片段)
...随机参数）的性质来防止深度过大。与普通treap不同的是非旋treap通过树的分裂与合并来实现这一点，而非旋转。核心操作Update如果是要实现类似于set<int>的功能，可以不用这一部分。本文以loj104为例，我们需要在这里更新节... 查看详情
非旋treap总结：快过splay好用过传统treap(代码片段)
非旋$Treap$其高级名字叫$FhqTreap$，既然叫$Treap$，它一定满足了$Treap$的性质（虽然可能来看这篇的人一定知道$Treap$，但我还是多说几句：$FhpTreap$就是继承了$Treap$的随机系统，在二叉搜索的基础上，每个点加一个随机化处理，这... 查看详情
$fhqtreap$(代码片段)
-$fhqTreap$与$Treap$的差异 $fhqTreap$是$Treap$的非旋版本，可以实现一切$Treap$操作，及区间操作和可持久化 $fhqTreap$非旋关键在于分裂与合并$(Split\&Merge)$-$Split$ 分裂相当于将一棵平衡树分为两棵平衡树，比如可以以值$x$... 查看详情
沉迷数据结构1(treap&非旋treap)
Achen大佬说不要沉迷数据结构否则智商会降低的。从省选考完后就开始学treap，首先是自己yy了一个打了两百多行，然后debug了2个月还是3个月记不清了。最后弃疗，去找了网上别人的代码抄了一遍。noip考完后补常规的一段时间，... 查看详情
jewelmagicuva-11996(代码片段)
JewelMagicUVA-11996这是一道用splay/非旋treap做的题（这里用的是非旋treap）1/2/3是splay/非旋treap的常规操作。对于操作4，可以用哈希法求LCP。记hash(i,L)为子串[i,i+L-1]（即第i个开始的L个）的hash值。记s[i]为序列第i位（编号从1开始），n... 查看详情
平衡树之非旋treap
平衡树（二叉树）线段树不支持插入or删除一个数于是平衡树产生了常见平衡树：treap（比sbt慢，好写吧），SBT(快，比较好写，有些功能不支持)，splay（特别慢，复杂度当做根号n来用，功能强大，不好写），rbt（红黑树，特别快... 查看详情
[bzoj3224]普通平衡树非旋treap
题意 维护一个多重集合$S$,支持: ①插入一个数$w$. ②删除一个数$w$. ③查询$w$在集合中的排名. ④查询集合中排名第$r$的数. ⑤求集合中$w$的前驱. ⑥求集合中$w$的后继. $Nle... 查看详情
treap学习小记(代码片段)
介绍treap是tree和heap的组合词，说明这种数据结构有树的特点又有堆的特点。本质是一颗二叉搜索树。treap的结点除了key关键字外还有个priority关键字。treap除了要保证key满足二叉搜索树性质，还要保证当前priority大于等于两个子节... 查看详情
treap模板(代码片段)
题目：https://www.luogu.org/problemnew/show/P3369Treap模板。代码如下：#include<iostream>#include<cstdio>#include<cstring>#include<algorithm>usingnamespacestd;intconstMAXN=100005,inf=1e9;i 查看详情
treap（树堆）详解(代码片段)
树堆(Treap)详解本篇随笔详细讲解一下一种随机化数据结构——树堆（(Treap)）。树堆的概念首先给一个字符串等式：[Treap=Tree+heap]所以(Treap)树堆其实就是树+堆。树是二叉查找树(BST)，堆是二叉堆，大根堆小根堆都可以。关于(BST)... 查看详情
treap(代码片段)
TREAPTreap=Tree+Heap.树堆，在数据结构中也称Treap，是指有一个随机附加域满足堆的性质的二叉搜索树，其结构相当于以随机数据插入的二叉搜索树。其基本操作的期望时间复杂度为O(logn)。相对于其他的平衡二叉搜索树，Treap的特点... 查看详情
treap模板(代码片段)
非指针Treap#include<bits/stdc++.h>#definefifirst#definesesecond#defineINF0x3f3f3f3f#definefioios::sync_with_stdio(false);cin.tie(0);cout.tie(0)#definepqueuepriority_queue#defineNEW(a,b)memset(a,b,s 查看详情
treap树(代码片段)
...》关于这个Treap树的原理和实现描述非常少，我就直接给代码吧，原理大家自己百度了。首先定义的个类template<typenameT>classtp_treepublic:typedefstruct_tp_type_tp_type(_tp_type*_p,_tp_type*_left,_tp_type*_ri 查看详情
treap(代码片段)
Treap=Tree+Heap，即在普通二叉查找树的基础上每个节点有了一个新值域：强化值（因为它将普通二叉查找树强化为treap就自己起了这个名字，是用来满足堆性质的，即后文说满足堆性质都指强化值满足堆性质）。要求这个树节... 查看详情
平衡树treap(代码片段)
Treap=BST+Heap,BST指的是二叉搜索树,而Heap指的是二叉堆,在此处我们使用的是小根堆. Treap上的每一个结点都维护六个值,一个是它本身的权值data,一个是用于维护堆的性质的权值key(他是随机赋上的一个值),那么我们为什么要给每一... 查看详情
来自上帝的骰子---treap(树堆)详解(代码片段)
...名查询值7.查询前驱后继8.销毁Treap9.迭代器的设计完整源代码Treap.hTreap.cpp测试AVLvsTreapvs普通BST为什么说是上帝的骰子？解释这个问题，首先由这个数据结构的名字开始，Tre 查看详情