信奥赛C++提高组csp-s之平衡树（Treap）

信奥赛C++提高组csp-s之平衡树（Treap）

平衡树概述

为什么需要平衡树？

二叉查找树（Binary Search Tree, BST）的查找、插入、删除操作时间复杂度为 O(h)，其中 h 为树的高度。在理想情况下，BST 的高度为 O(log n)，但在最坏情况下（例如插入的节点序列本身有序），BST 会退化成单链表，性能下降到 O(n)。

平衡树的核心思想是在进行插入和删除操作时，通过旋转或重构等方式保持树的高度始终维持在 O(log n) 量级，从而保证所有操作的时间复杂度稳定在 O(log n)。

常见平衡树类型

常见的平衡树包括：

其中，Treap是CSP-S考场中最常用的平衡树。本文将以 Treap 为核心进行讲解。

Treap核心知识点详解

Treap（树堆）是一种结合了二叉搜索树（BST）和堆特性的平衡树结构。它通过为每个节点赋予一个随机的优先级（pri），并利用旋转操作来同时维护BST的有序性和堆的优先级，从而实现了期望的平衡复杂度，非常适合CSP-S竞赛中快速编写和调试。

1. 数据结构定义

// 用数组模拟静态树，速度更快intv[N];// 节点的值 (key)intp[N];// 随机优先级 (priority)intl[N];// 左儿子intr[N];// 右儿子intsz[N];// 子树大小intct[N];// 当前值的重复个数

• 存储方式：采用数组模拟而非结构体或指针，这能大幅提升运行效率。
• 逻辑结构：每个节点存储v值来维护BST性质，同时存储一个随机生成的p值来维护大根堆性质。
• 子树大小sz：用于高效地查询排名和第k大的数。当节点值重复时，我们将其计数ct累加，而不是插入多个相同节点，这能显著简化删除操作并节省空间。

2. 核心操作原理

案例研究：普通平衡树

题目描述

您需要动态地维护一个可重集合M MM，并且提供以下操作：

1. 向M MM中插入一个数x xx。
2. 从M MM中删除一个数x xx。（若有多个相同的数，应只删除一个）
3. 查询M MM中有多少个数比x xx小，并且将得到的答案加1 11。
4. 查询如果将M MM从小到大排列后，排名位于第x xx位的数。
5. 查询M MM中x xx的前驱（定义为M MM中小于x xx，且最大的数）。
6. 查询M MM中x xx的后继（定义为M MM中大于x xx，且最小的数）。

对于操作3 , 5 , 6 3,5,63,5,6，不保证当前可重集中存在数x xx。

对于操作4 , 5 , 6 4,5,64,5,6，保证答案一定存在。

输入格式

第一行为n nn，表示操作的个数，下面n nn行每行有两个数opt \text{opt}opt和x xx，opt \text{opt}opt表示操作的序号（$ 1 \leq \text{opt} \leq 6 $）。

输出格式

对于操作3 , 4 , 5 , 6 3,4,5,63,4,5,6每行输出一个数，表示对应答案。

输入输出样例 1

输入 1

10 1 106465 4 1 1 317721 1 460929 1 644985 1 84185 1 89851 6 81968 1 492737 5 493598

输出 1

106465 84185 492737

【数据范围】

对于100 % 100\%100%的数据，1 ≤ n ≤ 10 5 1\le n \le 10^51≤n≤105，∣ x ∣ ≤ 10 7 |x| \le 10^7∣x∣≤107。

思路分析（旋转 Treap）

1. 节点设计：每个节点包含左子、右子、值、出现次数、子树大小、随机优先级。子树大小用于快速求排名和第 k 小。
2. 旋转操作：右旋和左旋用于维护堆性质（优先级大的在上）。旋转后需更新相关节点的子树大小。
3. 插入：递归查找插入位置，若值已存在则增加计数；否则新建节点。插入后若子节点优先级大于父节点，则通过旋转将子节点上提。
4. 删除：递归找到目标节点。若计数 >1 则减一；否则若只有一个孩子或没有孩子，则直接替换；若有两个孩子，则通过旋转将优先级大的孩子旋到当前节点位置，再递归删除该值（此时目标值已到旋转后的子树上）。
5. 查询排名：根据 BST 性质，比较当前节点值与目标值，递归计算左子树大小并累加。
6. 查询第 k 小：利用左子树大小判断目标所在区间，递归查找。
7. 前驱/后继：递归查找小于 x 的最大值 / 大于 x 的最小值。

所有操作时间复杂度 O(log n)，空间复杂度 O(n)。

代码实现

#include<bits/stdc++.h>usingnamespacestd;constintN=100010;constintINF=1e9+10;// 用于前驱后继的边界structNode{intl,r;// 左右子节点下标intv;// 节点值intc;// 该值出现次数ints;// 子树大小（含重复计数）intp;// 随机优先级}t[N];intrt,tot;// 根节点编号，节点总数// 更新节点 u 的子树大小voidupd(intu){t[u].s=t[t[u].l].s+t[t[u].r].s+t[u].c;}// 右旋（以 u 为轴，将左孩子旋上来）voidrot_r(int&u){intl=t[u].l;t[u].l=t[l].r;t[l].r=u;upd(u);upd(l);u=l;}// 左旋（以 u 为轴，将右孩子旋上来）voidrot_l(int&u){intr=t[u].r;t[u].r=t[r].l;t[r].l=u;upd(u);upd(r);u=r;}// 插入值 v，u 为当前子树根引用voidins(int&u,intv){if(!u){u=++tot;t[u]={0,0,v,1,1,rand()};return;}if(v==t[u].v){t[u].c++;upd(u);return;}if(v<t[u].v){ins(t[u].l,v);if(t[t[u].l].p>t[u].p)rot_r(u);}else{ins(t[u].r,v);if(t[t[u].r].p>t[u].p)rot_l(u);}upd(u);}// 删除一个值 v（只删一个）voiddel(int&u,intv){if(!u)return;if(v==t[u].v){if(t[u].c>1){t[u].c--;upd(u);return;}// 节点无孩子或只有一个孩子if(!t[u].l||!t[u].r){u=t[u].l+t[u].r;return;}// 两个孩子，将优先级大的孩子旋上来，然后递归删除if(t[t[u].l].p>t[t[u].r].p){rot_r(u);del(t[u].r,v);}else{rot_l(u);del(t[u].l,v);}upd(u);return;}if(v<t[u].v)del(t[u].l,v);elsedel(t[u].r,v);upd(u);}// 查询比 v 小的数的个数 +1（即 v 的排名）intrk(intu,intv){if(!u)return1;// 空树，v 排名为 1if(v<=t[u].v)returnrk(t[u].l,v);returnt[t[u].l].s+t[u].c+rk(t[u].r,v);}// 查询排名为 k 的数（k 从 1 开始）intkth(intu,intk){while(u){if(k<=t[t[u].l].s)u=t[u].l;elseif(k<=t[t[u].l].s+t[u].c)returnt[u].v;else{k-=t[t[u].l].s+t[u].c;u=t[u].r;}}return0;// 题目保证有解}// 查询 v 的前驱（小于 v 的最大数）intpre(intu,intv){intres=-INF;while(u){if(v<=t[u].v)u=t[u].l;else{res=max(res,t[u].v);u=t[u].r;}}returnres;}// 查询 v 的后继（大于 v 的最小数）intsuc(intu,intv){intres=INF;while(u){if(v>=t[u].v)u=t[u].r;else{res=min(res,t[u].v);u=t[u].l;}}returnres;}intmain(){srand(time(0));intn;scanf("%d",&n);while(n--){intop,x;scanf("%d%d",&op,&x);if(op==1)ins(rt,x);elseif(op==2)del(rt,x);elseif(op==3)printf("%d\n",rk(rt,x));elseif(op==4)printf("%d\n",kth(rt,x));elseif(op==5)printf("%d\n",pre(rt,x));elseif(op==6)printf("%d\n",suc(rt,x));}return0;}

功能分析

• 插入 (ins)：递归插入，若值已存在则增加计数；否则新建节点。通过旋转维持大根堆性质，保证树高期望 O(log n)。
• 删除 (del)：递归删除，若计数 >1 则减一；若只有一个孩子则直接替换；若有两个孩子则通过旋转将优先级大的孩子旋到当前节点，再递归删除目标值。
• 查询排名 (rk)：利用 BST 性质，递归统计比 x 小的节点个数，最终结果加 1 即为排名。
• 查询第 k 小 (kth)：根据左子树大小与当前节点计数决定往左、返回当前、或往右查找。
• 前驱 (pre)：循环查找小于 x 的最大值。
• 后继 (suc)：循环查找大于 x 的最小值。

更多系列知识，请查看专栏：《信奥赛C++提高组csp-s知识详解及案例实践》：
https://blog.csdn.net/weixin_66461496/category_13113932.html

各种学习资料，助力大家一站式学习和提升！！！

#include<bits/stdc++.h>usingnamespacestd;intmain(){cout<<"########## 一站式掌握信奥赛知识! ##########";cout<<"############# 冲刺信奥赛拿奖! #############";cout<<"###### 课程购买后永久学习，不受限制! ######";return0;}

1、csp信奥赛高频考点知识详解及案例实践：

CSP信奥赛C++动态规划：
https://blog.csdn.net/weixin_66461496/category_13096895.html点击跳转

CSP信奥赛C++标准模板库STL：
https://blog.csdn.net/weixin_66461496/category_13108077.html 点击跳转

信奥赛C++提高组csp-s知识详解及案例实践：
https://blog.csdn.net/weixin_66461496/category_13113932.html

2、csp信奥赛冲刺一等奖有效刷题题解：

信奥赛C++普及组csp-j初赛&复赛真题题解（持续更新）https://blog.csdn.net/weixin_66461496/category_12808781.html 点击跳转

信奥赛C++提高组csp-s初赛&复赛真题题解（持续更新）
https://blog.csdn.net/weixin_66461496/category_13125089.html

3、GESP C++考级真题题解：

GESP(C++ 一级+二级+三级)真题题解（持续更新）：https://blog.csdn.net/weixin_66461496/category_12858102.html 点击跳转

GESP(C++ 四级+五级+六级)真题题解（持续更新）：https://blog.csdn.net/weixin_66461496/category_12869848.html 点击跳转

GESP(C++ 七级+八级)真题题解（持续更新）：
https://blog.csdn.net/weixin_66461496/category_13117178.html

4、csp/信奥赛C++，完整信奥赛系列课程（永久学习）：

https://edu.csdn.net/lecturer/7901 点击跳转

· 文末祝福 ·

#include<bits/stdc++.h>usingnamespacestd;intmain(){cout<<"跟着王老师一起学习信奥赛C++";cout<<" 成就更好的自己！ ";cout<<" csp信奥赛一等奖属于你! ";return0;}