信奥赛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树堆利用随机优先级维持堆性质简单易写权值平衡树P3369、可持久化P3835Splay通过伸展操作将访问节点旋至根常数较大但功能强大区间操作P3391、序列维护P2596替罪羊树通过暴力重构维持平衡无需旋转代码简单、避免复杂旋转逻辑SBT通过维护子树大小实现平衡动态顺序统计其中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. 核心操作原理操作主要代码原理说明旋转void rot(int u, int d)在不破坏BST中序遍历顺序的前提下通过左旋/右旋改变父子关系。例如右旋会将左子节点提升为父节点以维护p值的堆性质。插入void ins(int u, int x)1. 若节点为空创建新节点。2. 若x等于当前v[u]增加计数ct。3. 若x小于v[u]递归插入左子树反之插入右子树。4. 回溯时若子节点优先级p大于当前节点p则执行旋转。删除void del(int u, int x)1. 若x等于v[u]且计数ct[u] 1则直接减少计数。2. 若计数为1则需要删除节点a. 若为叶子节点或只有一个子节点直接删除。b. 若有两个子节点则将优先级较高的子节点旋转上来然后递归删除。查排名int rk(int u, int x)1. 若x v[u]向左子树递归。2. 若x v[u]排名为sz[l[u]] 1。3. 若x v[u]排名为sz[l[u]] ct[u] rk(r[u], x)。查第k大int kth(int u, int k)1. 若k sz[l[u]]在左子树中找。2. 若sz[l[u]] k sz[l[u]] ct[u]答案就是v[u]。3. 否则在右子树中找第k - sz[l[u]] - ct[u]大的数。前驱/后继int pre(int u, int x)利用BST性质递归查找前驱为严格小于x的最大值后继为严格大于x的最小值。案例研究普通平衡树题目描述您需要动态地维护一个可重集合M MM并且提供以下操作向M MM中插入一个数x xx。从M MM中删除一个数x xx。若有多个相同的数应只删除一个查询M MM中有多少个数比x xx小并且将得到的答案加1 11。查询如果将M MM从小到大排列后排名位于第x xx位的数。查询M MM中x xx的前驱定义为M MM中小于x xx且最大的数。查询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 xxopt \text{opt}opt表示操作的序号$ 1 \leq \text{opt} \leq 6 $。输出格式对于操作3 , 4 , 5 , 6 3,4,5,63,4,5,6每行输出一个数表示对应答案。输入输出样例 1输入 110 1 106465 4 1 1 317721 1 460929 1 644985 1 84185 1 89851 6 81968 1 492737 5 493598输出 1106465 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节点设计每个节点包含左子、右子、值、出现次数、子树大小、随机优先级。子树大小用于快速求排名和第 k 小。旋转操作右旋和左旋用于维护堆性质优先级大的在上。旋转后需更新相关节点的子树大小。插入递归查找插入位置若值已存在则增加计数否则新建节点。插入后若子节点优先级大于父节点则通过旋转将子节点上提。删除递归找到目标节点。若计数 1 则减一否则若只有一个孩子或没有孩子则直接替换若有两个孩子则通过旋转将优先级大的孩子旋到当前节点位置再递归删除该值此时目标值已到旋转后的子树上。查询排名根据 BST 性质比较当前节点值与目标值递归计算左子树大小并累加。查询第 k 小利用左子树大小判断目标所在区间递归查找。前驱/后继递归查找小于 x 的最大值 / 大于 x 的最小值。所有操作时间复杂度 O(log n)空间复杂度 O(n)。代码实现#includebits/stdc.husingnamespacestd;constintN100010;constintINF1e910;// 用于前驱后继的边界structNode{intl,r;// 左右子节点下标intv;// 节点值intc;// 该值出现次数ints;// 子树大小含重复计数intp;// 随机优先级}t[N];intrt,tot;// 根节点编号节点总数// 更新节点 u 的子树大小voidupd(intu){t[u].st[t[u].l].st[t[u].r].st[u].c;}// 右旋以 u 为轴将左孩子旋上来voidrot_r(intu){intlt[u].l;t[u].lt[l].r;t[l].ru;upd(u);upd(l);ul;}// 左旋以 u 为轴将右孩子旋上来voidrot_l(intu){intrt[u].r;t[u].rt[r].l;t[r].lu;upd(u);upd(r);ur;}// 插入值 vu 为当前子树根引用voidins(intu,intv){if(!u){utot;t[u]{0,0,v,1,1,rand()};return;}if(vt[u].v){t[u].c;upd(u);return;}if(vt[u].v){ins(t[u].l,v);if(t[t[u].l].pt[u].p)rot_r(u);}else{ins(t[u].r,v);if(t[t[u].r].pt[u].p)rot_l(u);}upd(u);}// 删除一个值 v只删一个voiddel(intu,intv){if(!u)return;if(vt[u].v){if(t[u].c1){t[u].c--;upd(u);return;}// 节点无孩子或只有一个孩子if(!t[u].l||!t[u].r){ut[u].lt[u].r;return;}// 两个孩子将优先级大的孩子旋上来然后递归删除if(t[t[u].l].pt[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(vt[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(vt[u].v)returnrk(t[u].l,v);returnt[t[u].l].st[u].crk(t[u].r,v);}// 查询排名为 k 的数k 从 1 开始intkth(intu,intk){while(u){if(kt[t[u].l].s)ut[u].l;elseif(kt[t[u].l].st[u].c)returnt[u].v;else{k-t[t[u].l].st[u].c;ut[u].r;}}return0;// 题目保证有解}// 查询 v 的前驱小于 v 的最大数intpre(intu,intv){intres-INF;while(u){if(vt[u].v)ut[u].l;else{resmax(res,t[u].v);ut[u].r;}}returnres;}// 查询 v 的后继大于 v 的最小数intsuc(intu,intv){intresINF;while(u){if(vt[u].v)ut[u].r;else{resmin(res,t[u].v);ut[u].l;}}returnres;}intmain(){srand(time(0));intn;scanf(%d,n);while(n--){intop,x;scanf(%d%d,op,x);if(op1)ins(rt,x);elseif(op2)del(rt,x);elseif(op3)printf(%d\n,rk(rt,x));elseif(op4)printf(%d\n,kth(rt,x));elseif(op5)printf(%d\n,pre(rt,x));elseif(op6)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各种学习资料助力大家一站式学习和提升#includebits/stdc.husingnamespacestd;intmain(){cout########## 一站式掌握信奥赛知识! ##########;cout############# 冲刺信奥赛拿奖! #############;cout###### 课程购买后永久学习不受限制! ######;return0;}1、csp信奥赛高频考点知识详解及案例实践CSP信奥赛C动态规划https://blog.csdn.net/weixin_66461496/category_13096895.html点击跳转CSP信奥赛C标准模板库STLhttps://blog.csdn.net/weixin_66461496/category_13108077.html 点击跳转信奥赛C提高组csp-s知识详解及案例实践https://blog.csdn.net/weixin_66461496/category_13113932.html2、csp信奥赛冲刺一等奖有效刷题题解信奥赛C普及组csp-j初赛复赛真题题解持续更新https://blog.csdn.net/weixin_66461496/category_12808781.html 点击跳转信奥赛C提高组csp-s初赛复赛真题题解持续更新https://blog.csdn.net/weixin_66461496/category_13125089.html3、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.html4、csp/信奥赛C完整信奥赛系列课程永久学习https://edu.csdn.net/lecturer/7901 点击跳转· 文末祝福 ·#includebits/stdc.husingnamespacestd;intmain(){cout跟着王老师一起学习信奥赛C;cout 成就更好的自己 ;cout csp信奥赛一等奖属于你! ;return0;}