一、二叉排序树 因为只是来讲treap的，所以关于二叉排序树的知识就不再赘述。 如果还不知道二叉排序树，可以先到别处学学再来看。 在二叉排序树中，我们将比该节点小的值放在该节点的左边，将比该节点大的值放在该节点的右边。 可是很显然，这样的话操作的时间复杂度就和树的深度有很大的关系。当树的形态为一条链的时候，就无法满足操作的复杂度为\(nlog(n)\)。 二、treap是什么 treap = tree + heap treap就是树与堆的结合体。为了防止树被单调的数据卡成一条链，可以给每个节点多加上一个随机的优先值，让树同时也满足堆的性质（一般为小根堆）。 由于优先值是随机的，所以树的深度平均为\(nlog(n)\)。 三、treap实现1、左旋（zig）与右旋（zag） 我们发现，在一个节点的优先值被随机生成后，树可能无法满足我们所要求的堆的性质。 所以为了让树同时也具备这个性质，需要对树进行一定的旋转，使树变成我们所希望的样子。 左旋：将根节点的右儿子作为根，根节点作为右儿子的左儿子。右旋：将根节点的左儿子作为根，根节点作为左儿子的右儿子。 由图中可知左旋与右旋的操作方法。
void up(int k) { //更新子树的大小 size[k] = size[lson[k]] + size[rson[k]] + c[k]; } void zig(int &k) { //左旋 int v = rson[k]; rson[k] = lson[v]; lson[v] = k; size[v] = size[k]; up(k); k = v; } void zag(int &k) { //右旋 int v = lson[k]; lson[k] = rson[v]; rson[v] = k; size[v] = size[k]; up(k); k = v; }2、插入操作 我们考虑在树上插入一个节点。 先像二叉排序树一样找到应当插入节点的位置，插入该节点，并初始化该节点的值。 由于树要满足小根堆的性质，所以如果插入的节点的优先级小于它的根节点，就通过左旋/右旋进行调整。（不理解的可以看看上面那张图）
void insert(int &k, int x) { //插入节点 if (k == 0) { //如果没有该节点，直接插入 k = ++ cnt; size[k] = c[k] = 1; a[k] = x; pri[k] = rand(); return; } size[k] ++; if (a[k] == x) c[k] ++; else if (x > a[k]) { insert(rson[k], x); if (pri[rson[k]] < pri[k]) zig(k); } else { insert(lson[k], x); if (pri[lson[k]] < pri[k]) zag(k); } }3、删除操作 考虑在树上删除一个节点。 首先先在树上找到该点。 对于这个点，有两种情况：要么它有一个或没有儿子，要么它有两个儿子。 先考虑只有一个或没有儿子的情况，显然这个点可以直接删除，将它的子树接到它的父节点上即可。 对于有两个儿子的情况，显然是不能直接删除这个点的。（因为无法确定左右子所应接在父节点上的位置） 所以对于有两个儿子的情况，可以通过左旋/右旋将待删除的点向叶子节点处旋转，直到只有一个或没有儿子为止。 在旋转时，如果改点的左儿子的优先级比右儿子小，就右旋；如果大，就左旋。
void del(int &k, int x) { //删除 if (k == 0) return; //没有该节点就直接退出 if (a[k] == x) { if (c[k] > 1) c[k] --, size[k] --; else { if (!lson[k] || !rson[k]) k = lson[k] + rson[k]; else if (pri[lson[k]] < pri[rson[k]]) zag(k), del(k, x); else zig(k), del(k, x); } } else if (x > a[k]) size[k] --, del(rson[k], x); else size[k] --, del(lson[k], x); }4、查询一个数的排名 查询排名，就是查询该数是这些数中第几小的。 查询排名的方法和二叉排序树一样，这里就不再说了。
int query_rank(int k, int x) { //查询排名 if (k == 0) return 2e9; if (a[k] == x) return size[lson[k]] + 1; if (x > a[k]) return size[lson[k]] + c[k] + query_rank(rson[k], x); else return query_rank(lson[k], x); }5、查询排名第x的数是什么 即是询问这些数中从小到大排后第x大的数是什么。 查询方法也和二叉排序树一样，直接放代码。
int query_num(int k, int x) { //查询排名为x的数 if (k == 0) return 2e9; if (x <= size[lson[k]]) return query_num(lson[k], x); x -= size[lson[k]]; if (x <= c[k]) return a[k]; x -= c[k]; return query_num(rson[k], x); }6、查询数x的前驱 即查询比x小的最大的数。 和二叉排序树一样。如果x比该数大，就往右走；否则往左走。
int query_pre(int k, int x) { //查询前驱 if (k == 0) return -2e9; if (a[k] < x) return max(a[k], query_pre(rson[k], x)); else return query_pre(lson[k], x); }7、查询数x的后继 即查询比x大的最小的数。 也和二叉排序树一样。如果x比该数小，就往左走；否则往右走。
int query_next(int k, int x) { //查询后继 if (k == 0) return 2e9; if (a[k] > x) return min(a[k], query_next(lson[k], x)); else return query_next(rson[k], x); }四、treap模板 放一题treap的模板题。bzoj3224
代码如下：
#include<cstdio> #include<algorithm> using namespace std; const int maxn = 100005; int n, cnt, root; int lson[maxn], rson[maxn], size[maxn], a[maxn], c[maxn], pri[maxn]; int read(void) { char c; while (c = getchar(), (c < '0' || c > '9') && c != '-'); int x = 0, y = 1; if (c == '-') y = -1; else x = c - '0'; while (c = getchar(), c >= '0' && c <= '9') x = x * 10 + c - '0'; return x * y; } int rand() { //生成随机数 static int seed = 2333; return seed = (int)((((seed ^ 998244353) + 19260817ll) * 19890604ll) % 1000000007); } void up(int k) { //更新子树的大小 size[k] = size[lson[k]] + size[rson[k]] + c[k]; } void zig(int &k) { //左旋 int v = rson[k]; rson[k] = lson[v]; lson[v] = k; size[v] = size[k]; up(k); k = v; } void zag(int &k) { //右旋 int v = lson[k]; lson[k] = rson[v]; rson[v] = k; size[v] = size[k]; up(k); k = v; } void insert(int &k, int x) { //插入节点 if (k == 0) { //如果没有该节点，直接插入 k = ++ cnt; size[k] = c[k] = 1; a[k] = x; pri[k] = rand(); return; } size[k] ++; if (a[k] == x) c[k] ++; else if (x > a[k]) { insert(rson[k], x); if (pri[rson[k]] < pri[k]) zig(k); } else { insert(lson[k], x); if (pri[lson[k]] < pri[k]) zag(k); } } void del(int &k, int x) { //删除 if (k == 0) return; //没有该节点就直接退出 if (a[k] == x) { if (c[k] > 1) c[k] --, size[k] --; else { if (!lson[k] || !rson[k]) k = lson[k] + rson[k]; else if (pri[lson[k]] < pri[rson[k]]) zag(k), del(k, x); else zig(k), del(k, x); } } else if (x > a[k]) size[k] --, del(rson[k], x); else size[k] --, del(lson[k], x); } int query_rank(int k, int x) { //查询排名 if (k == 0) return 2e9; if (a[k] == x) return size[lson[k]] + 1; if (x > a[k]) return size[lson[k]] + c[k] + query_rank(rson[k], x); else return query_rank(lson[k], x); } int query_num(int k, int x) { //查询排名为x的数 if (k == 0) return 2e9; if (x <= size[lson[k]]) return query_num(lson[k], x); x -= size[lson[k]]; if (x <= c[k]) return a[k]; x -= c[k]; return query_num(rson[k], x); } int query_pre(int k, int x) { //查询前驱 if (k == 0) return -2e9; if (a[k] < x) return max(a[k], query_pre(rson[k], x)); else return query_pre(lson[k], x); } int query_next(int k, int x) { //查询后继 if (k == 0) return 2e9; if (a[k] > x) return min(a[k], query_next(lson[k], x)); else return query_next(rson[k], x); } int main() { n = read(); while (n --) { int opt = read(), x = read(); if (opt == 1) insert(root, x); else if (opt == 2) del(root, x); else if (opt == 3) printf("%d\n", query_rank(root, x)); else if (opt == 4) printf("%d\n", query_num(root, x)); else if (opt == 5) printf("%d\n", query_pre(root, x)); else if (opt == 6) printf("%d\n", query_next(root, x)); } return 0; }转载于:https://www.cnblogs.com/Gaxc/p/10123505.html
相关资源：数据结构之Treap详解