非旋 treap 结构体数组版（无指针）详解，有图有真相
非旋 $treap$ （FHQ treap）的简单入门
前置技能
建议在掌握普通 treap 以及 左偏堆（也就是可并堆）食用本blog
原理
以随机数维护平衡，使树高期望为logn级别， FHQ 不依靠旋转，只有两个核心操作merge（合并）和split（拆分）
所谓随机数维护平衡就是给每个节点一个随机值 key （下文中没有加随机的就代表是真实权值），
然后整棵树中 key 值要满足小（大）根堆的性质（也就是heap），
同时也要满足平衡树（tree）的性质（也就是每个节点左子树内节点真实权值小于它，右子树相反）
然后这个玩意儿就有了一个草率的名字：treap （tree 和 heap 的结合体）
结构体变量介绍
核心操作
merge操作
模型实现
假设有两颗子树x，y，且 x 的所有节点的值都小于 y 的所有节点的值，随机权值 key 都以小根堆的形式存储。
此时要合并 x 和 y 。我们先比较它们的根的随机权值，发现1<3，因为要满足小根堆性质，于是 x 的左子树全部不变，让它的右子树继续和 y 合并。
这时我们发现，随机权值 key 5>3，所以 y 接到 rot 的下方，成为 rot 的右儿子，y的右子树全部不变，让y的左子树继续和x合并（以满足平衡树的性质）。
由于5>4，所以y和y的右子树作为rot的左儿子，y的左子树继续和x合并。
5<7，所以接入x和它的左子树作为rot的左儿子。
至此，我们发现 x 为 0 ，所以直接返回 y ，合并结束。
代码实现
split操作
split有两种拆分方式:
1. 按权值大小拆分
2. 按排名大小拆分。
模型实现
1.按权值split
首先得有个基准值 a ，即权值小于等于 a 的节点全部进入左树（下图中会将此类节点染红），大于a的节点全部进入右树（下图中会将此类节点染蓝）。这里以a=25为例。
首先，发现rot的权值=15<25，由平衡树的性质可知，rot的左子树所有节点权值一定小于25，所以rot和它的的左子树全部进入左树，继续拆分rot的右子树。
32>25，所以 rot 和它的右子树全部进入右树，继续拆分 rot 的左子树。
29>25，同上。
24<25，所以拆分右子树。
27>25，所以拆分左子树。
发现此时rot为0，所以拆分完毕，返回。
2.按排名split
就是把前 k 个节点拆入左树，其它节点拆入右树。这里以k=5为例。
rot的左子树的siz+1=3<5，所以rot和它的左子树进入左树，其他节点拆分5-3=2个节点进入左树。
4+1>2，所以rot和右子树进入右树，其它节点继续拆分出2个节点进入左树。
3+1>2，同上。
1+1=2，所以rot和左子树进入左树，其它节点继续拆分2-2=0个节点进入左树。
1+0>0，所以rot和右子树进入右树，其它节点继续拆分0个节点进入左树。
rot为0，拆分结束。
代码实现
1.按权值split
2.按排名split
其他操作
FHQ treap 的核心操作只有 merge 和 split 两个，其他操作都是基于这两个操作实现的。
插入
插入权值为 x 的节点时，先新建一个节点，再以 x 为界按权值 split 整棵树为a,b，再按顺序 merge a，x，b。
代码实现
删除
要删除x，先将整棵树以 x-1 为界按权值split 成a和b，再将 b 以 1 为界 按排名split 成c和d，则 c 就是要删除的节点。最后按顺序merge a，b，d。
（当然，这是在要删除节点必定存在的情况下才能进行的操作，不存在的情况请自行脑补）
代码实现
查询 x 的排名
先将整棵树以x-1按权值split成a和b，则a的siz+1即为x的排名。
代码实现
查询排名为 k 的值
先split出整棵树前k-1小节点，则右树最小节点即为所求节点，再次split 即可。
代码实现
查x前驱
将整棵树以x-1按权值split，左树中最大节点即为所求节点，转入第x小值问题。
代码实现
查x后继
将整棵树以x按权值split，右树中最小节点即为所求节点，转入第x小值问题。
代码实现
非旋 Treap的其他作用
非旋 trap 是支持区间操作的，具体其实就是你把原来的一棵树 split 成 3 棵树（$1~l-1,l~r,r+1~n$），然后 我们对中间那棵树进行操作即可，具体代码不附上了
例题
代码
感谢 axjcy 大佬的 blog