例题链接

例题加强版链接

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

插入一个数 $x$。

删除一个数 $x$（若有多个相同的数，应只删除一个）。

定义排名为比当前数小的数的个数 $+1$。查询 $x$ 的排名。

查询数据结构中排名为 $x$ 的数。

求 $x$ 的前驱（前驱定义为小于 $x$，且最大的数）。

求 $x$ 的后继（后继定义为大于 $x$，且最小的数）。

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

约定

为了规范，我们约定：

本文所有指针均表示使用数组实现的静态指针，当然，可以改成动态指针；
指针指向 $0$ 表示不存在；
“树 $p$”表示以 $p$ 为根节点的树；
$left_x$ 表示 $x$ 的左子节点；
$right_x$ 表示 $x$ 的右子节点；
$value_x$ 表示 $x$ 的权值；
$size_x$ 表示以 $x$ 为根的子树大小；
$rand_x$ 表示 $x$ 的随机优先级（解释见下文）；
整棵 FHQ Treap 的树根为 $root$（详见下文）；
本文仅讨论值域为整数的 FHQ Treap，因为实数或是其他数据仅仅需要微调即可。

而在代码中就表现为：

struct node{
    int value,rand,size;
    int left,right;
}t[N+1];

平衡树

什么是平衡树呢？

首先你需要了解二叉搜索树。

那么，二叉搜索树又是什么呢？

简单而言，就是一棵二叉树，满足对于任意节点 $x$，其左、右节点 $l_x,r_x$ 满足 $value_{l_x}<value_x<value_{r_x}$。（当然，大于也行，但本文讨论的是小于）

这样我们便可以很方便的作树上查找等处理，但是这样有可能会被卡成一条长度接近于 $n$ 的单链（令节点数为 $n$），最终时间复杂度退化为 $\mathcal O(n)$。

因此，平衡树应运而生。

平衡树通过一些操作来使得从根节点出发的单链长度为 $\mathcal O(\log_2n)$，从根节点到任意叶节点的路径长度差不超过 $1$。

这些操作包括但不限于：旋转（如“Splay 树”、“Treap”）、重构（如“替罪羊树”）、分裂与合并（如“FHQ Treap”）。

FHQ Treap（无旋 Treap）

命名由来

因为 FHQ Treap 由范浩强发明。因此名为“FHQ Treap”。

Treap 特征

无论是旋转式Treap 还是 FHQ Treap，都同时满足二叉搜索树的性质与堆的性质。

具体而言，Treap 在维护基本权值的同时还维护了一个随机优先级，权值满足二叉搜索树的性质，优先级满足堆的性质（大根堆和小根堆随意）。

即对于任意节点 $x$ 只要 $left_x,right_x$ 均存在就同时满足：

\[\large value_{left_x}\leq value_x<value_{right_x}\\ \large rand_{x}>rand_{left_x},rand_{right_x}\]

如图是一个 Treap 的示例：

图片来源：OI Wiki

基本操作

分裂与合并。

分裂

具体而言，就是将以 $p$ 为根的树以 $x$ 为键值分裂为两棵二叉搜索树，一棵以 $l$ 为根节点且最大权值小于等于 $x$，一棵以 $r$ 为根节点且最小权值大于 $x$。

令 $V_l,V_r$ 表示树 $l$ 、树 $r$ 的节点集合，则分裂后：对于 $\forall t\in V_l$ 有 $value_t\leq x$，对于 $\forall t\in V_r$ 有 $value_t>x$。

我们不妨将一棵树简化为三部分：根节点、左子树、右子树。

那么我们拿 $x$ 与根节点的权值 $value_p$ 比较即可。

以 $value_p\leq x$ 时为例。$value_p>x$ 时同理可得。

此时说明我们应该将 $p$ 放入树 $l$。因为 $p$ 的权值 $value_p$ 满足“对于 $\forall t\in V_l$ 有 $value_t\leq x$”。同时树 $left_p$ 也应该被放入树 $l$，因为这原本就是一棵二叉搜索树。

然后呢？右子树如何处理？

要知道，右子树中很有可能存在节点 $q$ 满足 $value_p\leq value_q \leq x$。也就是说，虽然 $q$ 的权值大于 $p$ 的权值（不然也不会在右子树），但是仍然小于 $x$ 的权值，应该被放入 $l$ 树。

如图：

图片来源：OI Wiki

那么我们就要找到所有满足此条件的 $q$。

怎么找？递归。

令 $split(p,x)$ 表示将以 $p$ 为根的树以 $x$ 为键值分裂为两棵树 $l,r$。

那么此时还需要 $split(right_p,x)$，分裂 $p$ 的右子树 $right_p$，为了方便表述令其分裂为两棵树 $l’,r’$。

$split()$ 需要返回的参数有两个：$l,r$。即分裂后左右子树各自根节点的指针。

那么在 $split(p,x)$ 中显然就有 $l\leftarrow p$。但是，$r$ 是什么呢？

不难发现，上文中所提及的所有满足条件的 $q$ 都应该被放入树 $l$。

那么我们在 $split(right_p,x)$ 中的 $r’$ 仍然为 $r$。应为 $split(right_p,x)$ 是在以 $right_p$ 为根的树中分裂，小于 $x$ 的节点会被放入 $l’$，而那正是我们想要的。

那么，$l’$ 如何处理呢？其实也不难，就是 $l’\leftarrow right_l$ 即 $l’\leftarrow right_p$。因为树 $l$ 中存储了所有权值小于等于 $x$ 的节点，而 $l’$ 同样满足此特性。同时这一整棵树都满足二叉查找树的性质，因此 $value_{l’}>value_l$，放入以后同样不违背性质。

当 $split(p,x)$ 遇到 $value_x>x$ 时，即 $r\leftarrow p$ 后 $split(left_p,x),l’\leftarrow l,r’\leftarrow left_p$ 即可。

实现代码

//事实上，如果返回一个结构体或是一个pair表示左右指针也是可以的，此处使用实参实现。
void split(int p,int x,int &l,int &r){
    if(p==0)l=r=0;
    else{
        if(t[p].value<=x){
            l=p;
            split(t[p].right,x,t[p].right,r);
        }else{
            r=p;
            split(t[p].left,x,l,t[p].left);
        }update(p);//update()函数见后文
    }
}

合并

与分裂的操作类似，定义 $merge(l,r)$ 表示将以树 $l$ 和树 $r$ 合并，返回一个值表示合并后新树的根节点的指针,保证树 $l$ 的节点最大权值小于树 $r$ 的节点最小权值。

当 $l=0$ 时，那就说明此时树 $l$ 不存在，无法合并，直接返回 $r$ 即可。对于 $r=0$ 时，同样直接返回 $l$ 即可，而这也是递归边界。（出现这种情况的原因见下文）

既然已经保证了树 $l$ 的权值小于树 $r$ 的权值，也就意味着将 $r$ 合并至 $right_l$ 和将 $l$ 合并至 $left_r$ 均可行。

那么这时的合并依据就是开头所提到的随机优先级，因为我们需要使优先级满足堆的性质，具体见“复杂度分析”。我们令优先级较大的节点成为优先级较小的节点的子树即可。

实现代码

int merge(int l,int r){
    if(l==0)return r;
    if(r==0)return l;
    if(t[l].rand<t[r].rand){
        t[l].right=merge(t[l].right,r);
        update(l);//作用同样见下文
        return l;
    }else{
        t[r].left=merge(l,t[r].left);
        update(r);//作用同样见下文
        return r;
    }
}

子树大小更新

定义 $update(p)$，对于给定的 $p$，$update(p)$ 会更新 $p$ 的子树大小。

即：$size_p\leftarrow size_{left_p}+size_{right_p}$。

其功能后面会解释。

之所以 $size_p$ 会改变，因为 FHQ Treap 的实现原理与平衡树的定义表明，一个节点的子节点不是一成不变的，那么 $size_p$ 自然也会改变。

实现代码

void update(int p){
    t[p].size=t[t[p].left].size+t[t[p].right].size+1;
}

功能实现

FHQ Treap 因为其独特的实现方式——合并与分裂——使得许多功能都十分简单。

插入数值

令待插入数值为 $x$。

创建节点

我们定义一个函数 $create(x)$，表示在新建一个权值为 $x$ 的节点。

实现非常简单，不过多赘述。（见约定部分）

实现代码

mt19937 Rand(time(0));//rand()效率低下，因此使用mt19937
//...
int create(int x){
    static int top;
    t[++top]={x,(int)Rand(),1,0,0};	
    return top;
}

插入节点

众所周知，单独一个节点是可以看成一棵只有根节点的树的。

那么如何将其插入 FHQ Treap 呢？

哎，这不就是合并两棵树吗？我们考虑将树 $root$ 和刚刚创建的节点合并。

但是不能够使用 $merge()$ 因为我们无法保证树 $root$ 的节点权值与 $x$ 的大小关系。

虽然看似无解，我们却有一种绝妙而暴力的方法：分裂后再合并。

具体而言，就是将树 $root$ 以 $x$ 为关键值分裂为两棵树 $l,r$，于是由 $split()$ 就有树 $l$ 的节点权值小于等于 $x$，树 $r$ 的节点权值大于 $x$。

那么我们将新建节点 $create(x)$ 与树 $l$ 合并，然后将合并出的树再与树 $r$ 合并即可。

但是需要注意不要忘记给 $root$ 重新赋值，因为 $split()$ 后 $root$ 已经失效，应当将两次合并结束之后的有效根重新赋值给 $root$。

即：$root\leftarrow merge(merge(root,create(x)),r)$。

实现代码

void insert(int x){
    int l,r;
    split(root,x,l,r);
    root=merge(merge(l,create(x)),r);
}

删除数值

令待删除数值为 $x$。

与插入数值类似，删除数值的主要思路如下：

以 $x$ 为键值将树 $root$ 分裂为树 $l$ 和树 $r$，则树 $l$ 中的权值小于等于 $x$，即：$split(root,x,l,r)$。
以 $x-1$ 为键值将树 $l$ 分裂为树 $l’$ 和树 $r’$，则树 $l’$ 中的权值小于等于 $x-1$，即小于 $x$，又考虑到原本树 $l$ 的节点权值小于等于 $x$，则树 $r’$ 中的节点权值只能为 $x$，即：$split(l,x-1,l’,r’)$。
在树 $r’$ 中删除一个节点即可完成删除一个 $x$ 的任务，一般来讲会合并树 $left_{r’}$ 和树 $right_{r’}$，即令 $r’\leftarrow merge(left_{r’},right_{r’})$，这样会直接忽略掉节点 $r’$，即删除了 $r’$。
合并树 $l’,r’,r$，然后给 $root$ 重新赋值，即：$root\leftarrow merge(merge(l’,r’),r)$。

注：删除全部的 $x$ 仅仅需要在第 $4$ 步中直接运行 $root\leftarrow merge(l’,r)$ 即可，这样就直接忽略了包含全部权值为 $x$ 的节点的树 $r’$。

实现代码

void remove(int x){
    int l,r,pl;//变量可以回收再利用
    split(root,x,l,r);
    split(l,x-1,l,pl);
    pl=merge(t[pl].left,t[pl].right);
    root=merge(merge(l,pl),r);
}

求指定值的排名

令指定值为 $x$，定义 $rank(x)$ 求 $x$ 的排名。

$x$ 的排名：比 $x$ 小的数的个数。

也就是说我们需要找出权值小于 $x$ 的节点个数。

我们以 $x-1$ 为键值将树 $root$ 分裂为两棵树 $l,r$。

那么答案就是 $size_l$。

因为由 $split()$，此时所有权值小于等于 $x-1$（即小于 $x$）的节点都在树 $l$ 内，满足排名的定义。

而这也正是上文 $update()$ 的作用：保持节点子树大小正确。

实现代码

int rank(int x){
    int l,r;
    split(root,x-1,l,r);
    int ans=t[l].size+1;
    root=merge(l,r);
    return ans;
}

求指定排名的值

令指定排名为 $k$，定义 $kth(k,p)$ 表示在树 $p$ 中查找排名为 $k$ 的值（参数 $p$ 的存在具有必要性，其可以用于求前驱、后继节点，而全局调用时默认 $p\leftarrow root$。）。

在本文所讨论的 FHQ Treap 中，排名为 $k$ 的值是第 $k$ 大的值。

显然，当 $k<1$ 或 $k>size_p$ 时，不存在排名为 $k$ 的值。前者是过小（排名小于 $1$），后者是过大（超过了总节点个数）。此时返回一个特殊值即可，视程序和个人习惯而定，本文取 $2^{31}-1$。

那么，到底如何求解呢？

由平衡树的性质，左子树的节点权值小于右子树的权值。

那么：

当 $k<size_{left_p}$ 时，所求值就在树 $left_p$ 中，我们令 $p\leftarrow left_p$ 即可。
当 $k=size_{left_p}$ 时，所求值明显就是 $value_p$，即节点 $p$ 就是权值第 $k$ 大的节点，$kth()$ 返回 $value_p$ 即可。
当 $k>size_{left_p}$ 时，这说明 $k$ 在右子树中。

我们当然可以使用 $size_{right_\ldots}$ 来讨论，但是那样就太复杂了。

我们直接令 $p\leftarrow right_p$，然后 $k\leftarrow k-size_{left_p}-1$ 即可。

说明：$k\leftarrow k-size_{left_p}-1$ “过滤”了树 $p$ 的左子树和根节点，此时继续查找 $kth(k,p)$ 即可。

但是，稍微一想就能够发现，$kth(k,p)$ 的递归是可以轻而易举地转化为循环的。

因此，为了一点常数优化，我们一般使用 while(true) 配合 break 实现，最后 return t[p].value 即可。

实现代码

int kth(int k,int p=root){
    if(k<1||k>t[p].size)return 2147483647;
    while(true){
        if(t[t[p].left].size+1==k)break;
        else if(k<t[t[p].left].size+1)p=t[p].left;
        else{
            k-=t[t[p].left].size+1;
            p=t[p].right;
        }
    }return t[p].value;
}

求前驱节点

令给定节点权值为 $x$。

那么，我们需要找的节点的权值就是最大且满足小于 $x$ 的节点权值。

我们以 $x-1$ 为键值分裂树 $root$ 为树 $l,r$，然后查找树 $l$ 的最大节点权值即可。

问题来了：最大节点权值如何找？

这就是定义 $kth(k,p)$ 而不是 $kth(k)$ 的用处了。

我们在树 $l$ 中查找最后一个节点，即 $kth(size_l,l)$。

最后不要忘记合并还原，即 $root\leftarrow merge(l,r)$。

实现代码

int prev(int x){
    int l,r;
    split(root,x-1,l,r);
    int ans=kth(t[l].size,l);
    root=merge(l,r);
    return ans;
}

求后继节点

令给定节点权值为 $x$。

与求前驱节点同理，以 $x$ 为键值分裂树 $root$ 为树 $l,r$，答案即 $kth(1,r)$，树 $r$ 的第一个节点。

实现代码

int next(int x){
    int l,r;
    split(root,x,l,r);
    int ans=kth(1,r);
    root=merge(l,r);
    return ans;
}

复杂度分析

严谨证明（来自OI Wiki）

由于 Treap 各种操作的复杂度都和所操作的结点的深度有关，我们首先证明，所有结点的期望高度都是 $\mathcal O\left(\log_2n\right)$。

记号约定

为了方便表述，我们约定：

$n$ 是节点个数。
Treap 结点中满足二叉搜索树性质的称为权值，满足堆性质的（也就是随机的）称为优先级。不妨设优先级满足小根堆性质。
$x_k$ 表示权值第 $k$ 小的节点。
$X_{i,j}$ 表示集合 ${x_i,x_{i+1},\cdots,x_{j-1},x_j}$，即按权值升序排列后第 $i$ 个到第 $j$ 个的节点构成的集合。
$\operatorname{dep}(x)$ 表示节点 $x$ 的深度。规定根节点的深度是 $0$。
$Y_{i,j}$ 是一个指示器随机变量，当 $x_i$ 是 $x_j$ 的祖先时值为 $1$，否则为 $0$。特别地，$Y_{i,i}=0$。
$\operatorname{Pr}(A)$ 表示事件 $A$ 发生的概率。

树高的证明

引理：$Y_{i,j}=1$ 当且仅当 $x_i$ 的优先级是 $X_{i,j}$ 中最小的。

引理的证明

证明：

若 $x_i$ 是根节点：由于优先级满足小根堆性质， $x_i$ 的优先级最小，并且对于任意的 $x_j$ ， $x_i$ 都是 $x_j$ 的祖先。
若 $x_j$ 是根节点：同理， $x_j$ 优先级最小，因此 $x_i$ 不是 $X_{i,j}$ 中优先级最小的；同时 $x_i$ 也不是 $x_j$ 的祖先。
若 $x_i$ 和 $x_j$ 在根节点的两个子树中（一左一右），那么根节点 $r\in X_{i,j}$ 。因此 $x_i$ 的优先级不可能是 $X_{i,j}$ 中最小的（因为根节点的比它小）。同时，由于 $x_i$ 和 $x_j$ 分属两个子树， $x_i$ 也不是 $x_j$ 的祖先。
若 $x_i$ 和 $x_j$ 在根节点的同一个子树中，此时可以将这个子树单独拿出来作为一棵新的 Treap，递归进行上面的证明即可。

由于结点 $x_i$ 的深度等于它祖先的个数，因此有

\[\operatorname{dep}(x_i)=\sum\limits_{k=1}^nY_{k,i}\]

那么根据期望的线性性，有

\[E(\operatorname{dep}(x_i))=E\left(\sum\limits_{k=1}^nY_{k,i}\right)=\sum\limits_{k=1}^nE(Y_{k,i})\]

由于 $Y_{k,i}$ 是指示器随机变量，它的期望就等于它为 $1$ 的概率，因此

\[E(\operatorname{dep}(x_i))=\sum\limits_{k=1}^n\operatorname{Pr}(Y_{k,i}=1)\]

那么根据引理，深度的期望可以转化成

\[E(\operatorname{dep}(x_i))=\sum\limits_{k=1}^n\operatorname{Pr}(x_k=\min X_{i,k}\land k\ne i)\]

又因为结点的优先级是随机的，我们假定集合 $X_{i,j}$ 中任何一个结点的优先级最小的概率都相同，那么

\[\begin{aligned} E(\operatorname{dep}(x_i))&=\sum\limits_{k=1}^n\operatorname{Pr}(x_k=\min X_{i,k}\land k\ne i)\\ &=\sum\limits_{k=1}^n\operatorname{Pr}(x_k=\min X_{i,k})-1\\ &=\sum\limits_{k=1}^n\frac1{\vert i-k\vert+1}-1\\ &=\sum\limits_{k=1}^{i-1}\frac1{i-k+1}+\sum\limits_{k=i+1}^n\frac1{k-i+1}\\ &=\sum\limits_{j=2}^{i}\frac1j+\sum\limits_{j=2}^{n-k+1}\frac1j\\ &\leq2\sum\limits_{2=2}^{n}\frac1j\\ &<2\sum\limits_{j=2}^n\int_{j-1}^j\frac1x{\rm d}x\\ &=2\int_{1}^n\frac1x{\rm d}x\\ &=2\ln n\\ &=\mathcal O(\log_2n) \end{aligned}\]

因此每个结点的期望高度都是 $\mathcal O(n\log_2n)$。

而朴素的二叉搜索树的操作的复杂度均是 $\mathcal O(h)$，同时 Treap 维护堆性质的复杂度也是 $\mathcal O(h)$ 的。因此 Treap 各种操作的期望复杂度都是 $\mathcal O(h)=\mathcal O(log_2n)$。

不严谨分析

随机优先级使得期望树高为 $\mathcal O(\log_2n)$，满足了平衡树的性质。而分裂、合并这两种基本操作的时间复杂度也就是 $\mathcal O(\log_2n)$。

故，各类操作复杂度均为 $\mathcal O(\log_2n)$。

区间操作

参见FHQ Treap 之区间操作

例题 AC 代码

//#include<bits/stdc++.h>
#include<algorithm> 
#include<iostream>
#include<cstring>
#include<iomanip>
#include<cstdio>
#include<string>
#include<vector>
#include<cmath>
#include<ctime>
#include<deque>
#include<queue>
#include<stack>
#include<list>
#include<random>
using namespace std;
const int N=1e5;
mt19937 Rand(time(0));
int root;
//封装FHQ Treap
struct treap{
	struct node{
		int value,rand,size;
		int left,right;
	}t[N+1];
	
	void update(int p){
		t[p].size=t[t[p].left].size+t[t[p].right].size+1;
	}
	void split(int p,int x,int &l,int &r){
		if(p==0)l=r=0;
		else{
			if(t[p].value<=x){
				l=p;
				split(t[l].right,x,t[l].right,r);
			}else{
				r=p;
				split(t[r].left,x,l,t[r].left);
			}update(p);
		}
	}
	int merge(int l,int r){
		if(l==0)return r;
		if(r==0)return l;
		if(t[l].rand<t[r].rand){
			t[l].right=merge(t[l].right,r);
			update(l);
			return l;
		}else{
			t[r].left=merge(l,t[r].left);
			update(r);
			return r;
		}
	}
	
	int create(int x){
		static int top;
		t[++top]={x,(int)Rand(),1,0,0};	
		return top;
	}
	void insert(int x){
		int l,r;
		split(root,x,l,r);
		root=merge(merge(l,create(x)),r);
	}
	void remove(int x){
		int l,r,pl;
		split(root,x,l,r);
		split(l,x-1,l,pl);
		pl=merge(t[pl].left,t[pl].right);
		root=merge(merge(l,pl),r);
	}
	int rank(int x){
		int l,r;
		split(root,x-1,l,r);
		int ans=t[l].size+1;
		root=merge(l,r);
		return ans;
	}
	int kth(int k,int p=root){
		if(k<1||k>t[p].size)return 2147483647;
		while(true){
			if(t[t[p].left].size+1==k)break;
			else if(k<t[t[p].left].size+1)p=t[p].left;
			else{
				k-=t[t[p].left].size+1;
				p=t[p].right;
			}
		}return t[p].value;
	}
	int prev(int x){
		int l,r;
		split(root,x-1,l,r);
		int ans=kth(t[l].size,l);
		root=merge(l,r);
		return ans;
	}
	int next(int x){
		int l,r;
		split(root,x,l,r);
		int ans=kth(1,r);
		root=merge(l,r);
		return ans;
	}
}t;
int main(){
	/*freopen("test.in","r",stdin);
	freopen("test.out","w",stdout);*/
	
	int n;
	scanf("%d",&n);
	while(n--){
		int op,x;
		scanf("%d %d",&op,&x);
		switch(op){
			case 1:t.insert(x);break;
			case 2:t.remove(x);break;
			case 3:printf("%d\n",t.rank(x));break;
			case 4:printf("%d\n",t.kth(x));break;
			case 5:printf("%d\n",t.prev(x));break;
			case 6:printf("%d\n",t.next(x));break;
		}
	}
	
	/*fclose(stdin);
	fclose(stdout);*/
	return 0;
}

约定

平衡树

FHQ Treap（无旋 Treap）

命名由来

Treap 特征

基本操作

分裂

实现代码

合并

实现代码

子树大小更新

实现代码

功能实现

插入数值

创建节点

实现代码

插入节点

实现代码

删除数值

实现代码

求指定值的排名

实现代码

求指定排名的值

实现代码

求前驱节点

实现代码

求后继节点

实现代码

复杂度分析

严谨证明（来自OI Wiki）

记号约定

树高的证明

引理：$Y_{i,j}=1$ 当且仅当 $x_i$ 的优先级是 $X_{i,j}$ 中最小的。

不严谨分析

区间操作

例题 AC 代码

CATALOG

FEATURED TAGS

FRIENDS