一、什么是FHQTreap
FHQTreap是一种基于Treap树的二叉搜索树，它在Treap树的基础上做了优化，可以实现快速的查找和插入操作。FHQTreap最大的特点是，它使用了两种随机性的策略来维护数列中的元素，一种是随机优先级值，一种是随机旋转。FHQTreap是由FHQ在2016年发明的，相较于其他数据结构而言，FHQTreap具有更优秀的时间和空间复杂度。
下面我们来看看如何实现FHQTreap。首先需要定义FHQTreap中存储的节点结构体：
struct Node {
int key, val;
int size, pri;
Node* ch[2];
Node(int K=0, int V=0) : key(K), val(V), size(1), pri(rand()) { ch[0] = ch[1] = NULL; }
};其中，key是存储的关键字，val是存储的值，size代表以该节点为根节点的子树大小，pri是节点的随机优先级值，ch数组用来存储该节点的左右儿子。在初始化Node结构体时，pri值为随机生成的。
二、如何实现FHQTreap树的查找
FHQTreap树的查找操作和二叉搜索树的查找操作类似，都是从根节点开始，按照二叉搜索树的规则查找左右儿子。不同之处在于，FHQTreap树通过比较节点的优先级值来进行查找操作。
导航函数find操作实现如下：
Node* find(Node* u, int v) {
while (u != NULL) {
if (u -> val == v) return u;
u = u -> ch[u -> key < v];
}
return u;
}这是一个标准的二叉搜索树的递归实现，它在每次递归时都会比较u节点和v的大小，返回左右子节点进行递归查找。不同之处在于，我们可以通过比较节点的优先级值来判断查找方向，先朝条件更优秀的方向查找。
三、如何实现FHQTreap树的插入
插入操作是FHQTreap树中的最重要操作，它使用了两种随机性策略：随机优先级值和随机旋转。先看看插入函数的基本写法：
void insert(Node* &u, Node* v) {
if (u == NULL) u = v;
else {
int k = (u -> key < v -> key);
insert(u -> ch[k], v);
u -> size = u -> ch[0] -> size + u -> ch[1] -> size + 1; // 更新节点的size
if (u -> ch[k] -> pri > u -> pri) rotate(u, k); // 旋转
}
}这是一个递归操作，在每个节点上进行比较，如果该节点为空，直接将v节点插入即可。否则，递归查找左右儿子，同时更新节点的sizesize值，以便于后续的操作。如果该节点的子节点的优先级大于它本身的优先级，进行旋转操作，使得树的平衡性得以维护。
旋转操作是FHQTreap树中的核心操作，它用来保证树的平衡性。旋转分为左旋和右旋。左旋操作如下：
void rotate(Node* &u, int k) {
Node* v = u -> ch[k];
u -> ch[k] = v -> ch[k ^ 1];
v -> ch[k ^ 1] = u;
u -> size = u -> ch[0] -> size + u -> ch[1] -> size + 1;
v -> size = v -> ch[0] -> size + v -> ch[1] -> size + 1;
u = v;
}在左旋操作中，我们先找到u节点和v节点，并将u的右节点指向v的左节点，v的左节点指向u，然后重新计算节点的size值。
右旋操作与左旋操作类似，这里不再赘述。
四、如何实现FHQTreap树的删除
删除操作是FHQTreap树中的另外一个重要操作，它用来将数列中的元素删除，在每次删除操作后，我们可以确保该节点已经不存在于树中了。
由于FHQTreap树的删除操作需要分为两步：将待删除节点旋转到叶节点，然后将其删除，我们需要先实现旋转到叶节点的操作。rotateUntilLeaf如下：
Node* rotateUntilLeaf(Node* u, int k) {
while (u -> ch[k] != NULL) {
if (u -> ch[k] -> ch[k ^ 1] != NULL) {
int dir = (u -> ch[k] -> ch[k ^ 1] -> pri > u -> ch[k] -> pri);
rotate(u -> ch[k], dir ^ 1);
}
rotate(u, k);
}
return u;
}在该操作中，我们从指定的节点开始，逐层旋转深入直到到达终止节点（即该节点的左右儿子均为空），期间我们还需要调整节点的优先级值，旋转方向等信息，以达到旋转的目的。
其中的删除函数erase如下：
void erase(Node* &u, int v) {
if (u == NULL) return;
if (u -> val == v) {
if (u -> ch[0] == NULL && u -> ch[1] == NULL) u = NULL;
else if (u -> ch[0] == NULL) u = u -> ch[1];
else if (u -> ch[1] == NULL) u = u -> ch[0];
else {
int k = (u -> ch[0] -> pri > u -> ch[1] -> pri);
rotate(u, k);
erase(u -> ch[k ^ 1], v);
}
}
else {
erase(u -> ch[u -> val < v], v);
}
if (u) u -> size = u -> ch[0] -> size + u -> ch[1] -> size + 1;
}该函数通过比较节点的值来进行查找，如果找到了待删除节点，那么将其旋转到树的叶子节点处，然后进行删除操作。最后更新节点的size信息即可。
五、FHQTreap的应用
FHQTreap是一种基于Treap树的二叉搜索树，它在Treap树的基础上做了优化，可以实现快速的查找和插入操作。FHQTreap最大的特点是，它使用了两种随机性的策略来维护数列中的元素，一种是随机优先级值，一种是随机旋转。相较于其他数据结构而言，FHQTreap具有更优秀的时间和空间复杂度。
FHQTreap的应用非常广泛，比如说用途一：实现单调队列。单调队列是一种特殊的队列，它支持两种操作：入队和出队。入队操作是将一个元素插入到队列尾部，而出队操作是将队列头部的元素弹出。FHQTreap可以使用双端队列来实现单调队列，并且其时间复杂度为O(1)。
比如说用途二：统计区间内的满足条件的元素个数。假设我们有一个序列A，需要统计A[1…n]中满足某个条件的元素数量，那么可以使用FHQTreap来解决。首先对序列A建立FHQTreap，然后对序列A中的每一个元素，查找FHQTreap中比它小的元素的数量，就是它在序列A中的rank值。以此来计算区间内的满足条件的元素数量，相比于暴力查找，时间复杂度有了明显的提升。
六、总结
本文介绍了FHQTreap的基础知识和操作，包括何为FHQTreap树、如何实现FHQTreap树的查找和插入操作、如何实现FHQTreap树的删除操作以及FHQTreap的常见应用。值得注意的是，FHQTreap的高效性是基于它使用了两种随机性的策略维护数列中的元素。学习FHQTreap需要较扎实的C++编程能力，同时还需要对Treap树的基本知识有所掌握。
