平衡树定义

先解释下平衡树，当时找资料找了半天才完全搞懂。
上图：

平衡树 = 平衡二叉树
平衡树 = 二叉搜索树 + 不同平衡树对于平衡的定义
而“平衡性”是为了使整体的查询高度满足在 $O(\log n)$ 。

Treap 定义

这一篇是平衡树中的 Treap 树，最简单的平衡树之一。

首先这是一颗二叉搜索树，满足 BST 性质（即左节点 < 当前节点 < 右节点），但如何保证其复杂度呢？就需要用到 Treap 中的左旋、右旋了，上图：

可以发现旋转过程中并没有改变平衡树的二叉搜索树的性质，因此可以通过一定的旋转让树的深度保持在 $O(\log n)$ 左右，使树更加平衡。

怎么做到呢？我们发现在随机数据下二叉搜索树是几乎接近平衡的，而 Treap 就是利用随机的思想创造平衡。可以在维护整个树时顺便给每个节点一个随机值，强行给其加入堆的性质，让每个节点的额外权值大于其子节点的额外权值。

这就是 Treap 的来源（Treap = tree + heap），本质上是一棵随机权值满足大根堆性质的 BST，可以以 $O(\log n)$ 的时间复杂度完成检索、插入、求前驱后继、删除节点等操作。

问题描述

P3369 【模板】普通平衡树

您需要写一种数据结构（可参考题目标题），来维护一些数，其中需要提供以下操作：

插入一个数 $x$。
删除一个数 $x$（若有多个相同的数，应只删除一个）。
定义排名为比当前数小的数的个数 $+1$。查询 $x$ 的排名。
查询数据结构中排名为 $x$ 的数。
求 $x$ 的前驱（前驱定义为小于 $x$，且最大的数）。
求 $x$ 的后继（后继定义为大于 $x$，且最小的数）。

对于操作 3,5,6，不保证当前数据结构中存在数 $x$。

这道题是平衡树的模板题，直接用 Treap 实现即可。

建树

为了避免边界问题，初始往树中插入 $-\infty, \infty$ 两个节点，以 $-\infty$ 为根，$\infty$ 为其右节点。

struct BST
{
	int l,r,val,dat,cnt,size;
}a[N];
int idx,root,n;
// 新增一个节点
int New(int v)
{	
	a[++idx].val = v;
	a[idx].dat = rand();//随机权值
	a[idx].cnt = a[idx].size = 1;//初始为 1
	return idx;
}
void build()
{
	New(-INF);New(INF);
	root = 1,a[1].r = 2;
	update(1);
}

旋转

左旋（zag）、右旋（zig）操作可以说是 Treap 树中最重要的部分了，也是 Treap 树的精髓。
设当前节点是 y,
左旋的过程中可以想象成当前节点的左儿子绕父节点旋转了上来，而 y 的左儿子由 x 的右儿子嫁接而来。
右旋也是一样的，只要记住了图，就可以照葫芦画瓢写出 zig、zag 的代码了：

void zig(int &p)
{ 
	int q = a[p].l;
	a[p].l = a[q].r,a[q].r = p,p = q; //p 是引用
	update(a[p].r);update(p); // 从下到上更新
}
void zag(int &p)
{
	int q = a[p].r;
	a[p].r = a[q].l,a[q].l = p,p = q;
	update(a[p].l);update(p);
}

插入

题目中给出的数可能重复，可以给每个节点增加一个 cnt，记录该数出现个数，可以比较方便地处理删除和插入操作。

新增节点：

// 新增一个节点
int New(int v)
{	
	a[++idx].val = v;
	a[idx].dat = rand();//随机权值
	a[idx].cnt = a[idx].size = 1;//初始为 1
	return idx;
}

JZTXT

平衡树——Treap

平衡树定义

Treap 定义

问题描述

建树

旋转

插入