信奥赛C++提高组csp-s之FHQ Treap

信奥赛C提高组csp-s之平衡树FHQ Treap什么是FHQ TreapFHQ Treap无旋Treap是一种基于Tree二叉搜索树 Heap堆的数据结构。它的核心特点是不需要旋转操作仅依靠**分裂(Split)和合并(Merge)**两个核心操作就能实现所有平衡树功能。这也是它相比Splay和有旋Treap的最大优势——代码短小、易于理解、支持可持久化。Treap中的每个节点都存储两个关键值val节点权值满足BST性质左子树所有节点val ≤ 当前val ≤ 右子树所有节点val和key随机优先级满足堆性质。随机优先级的引入使得树的高度在期望上保持O(log n)从而保证所有操作的复杂度为O(log n)。FHQ Treap所有操作插入、删除、查询排名、查询第k大、前驱、后继、区间翻转等都可以通过组合split和merge来完成。1.1 数据结构存储每个节点存储左右儿子编号、节点权值val、随机优先级key、子树大小size用于按size分裂和排名查询。1.2 核心操作一分裂Split分裂操作将一棵树按权值或按size分成两棵树左树包含所有val ≤ pivot的节点右树包含所有val pivot的节点。实现逻辑从根节点开始遍历若当前节点val ≤ pivot则将该节点及左子树归入左树然后递归处理右子树否则归入右树递归处理左子树。每次递归后更新节点size。1.3 核心操作二合并Merge合并操作将两棵树合并为一棵前提是左树中所有节点的val都小于等于右树中所有节点的val。合并时比较两棵树根的key优先级key小的作为新树的根小根堆然后递归合并子树。1.4 为什么无旋Treap是平衡的FHQ Treap的平衡性来源于随机优先级——合并时完全按照优先级大小决定树的形态不受插入顺序的影响。由于优先级随机树的期望高度为O(log n)保证了操作效率。案例研究普通平衡树题目描述您需要动态地维护一个可重集合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。思路分析FHQ Treap本题要求动态维护一个可重集支持插入、删除、查排名、查第k小、查前驱、查后继六种操作。使用FHQ Treap无旋 Treap实现它基于分裂split和合并merge两个核心操作代码短、易于理解且能完美处理重复元素。核心设计每个节点存储值val、随机优先级pri、重复次数cnt、子树总大小sz即cnt之和、左右儿子l, r。用数组模拟节点0表示空节点。分裂split(u, key, x, y)将树u按值key分成两棵树x和y其中x中所有节点的值≤ keyy中所有节点的值 key。合并merge(x, y)合并两棵树要求x中所有值 ≤y中所有值按优先级维持堆性质。更新update(u)计算sz[u] sz[l] sz[r] cnt[u]。各操作实现方法插入 x按x-1和x分裂成三部分L x、M x、R x。若M非空则增加cnt否则新建节点。最后合并L, M, R。删除 x同样分裂成L, M, R。若M的cnt 1则cnt--否则丢弃M不合并。最后合并L, M, R。查询比 x 小的数的个数 1按x-1分裂成L x和R≥ x。答案 sz[L] 1。合并L, R。查询排名为 k 的数从根开始递归若左子树大小 ≥ k则进入左子树否则减去左子树大小和当前节点重复次数进入右子树。查询 x 的前驱小于 x 的最大数按x-1分裂成L x和R≥ x。在L中一直向右走找到最大值。合并。查询 x 的后继大于 x 的最小数按x分裂成L≤ x和R x。在R中一直向左走找到最小值。合并。所有操作时间复杂度均为O(log n)空间复杂度O(n)。代码实现#includebits/stdc.husingnamespacestd;constintN100010;// 最大操作次数intn,rt;// rt 为根节点编号structNode{intl,r;// 左右儿子编号intval,pri;// 值、随机优先级intcnt,sz;// 重复次数、子树大小cnt之和}tr[N];// 更新节点 u 的子树大小voidupd(intu){tr[u].sztr[tr[u].l].sztr[tr[u].r].sztr[u].cnt;}// 创建新节点返回编号intadd(intv){staticintidx0;intuidx;tr[u]{0,0,v,rand(),1,1};returnu;}// 分裂将以 u 为根的树按值 key 分成 x≤key和 ykeyvoidsplit(intu,intkey,intx,inty){if(!u){xy0;return;}if(tr[u].valkey){xu;split(tr[u].r,key,tr[u].r,y);}else{yu;split(tr[u].l,key,x,tr[u].l);}upd(u);}// 合并将 x 和 y 两棵树合并x 中所有值 ≤ y 中所有值intmerge(intx,inty){if(!x||!y)returnx|y;if(tr[x].pritr[y].pri){// 优先级小的作为根小根堆tr[x].rmerge(tr[x].r,y);upd(x);returnx;}else{tr[y].lmerge(x,tr[y].l);upd(y);returny;}}// 查询第 k 小的数k 从 1 开始intkth(intu,intk){while(u){intlsztr[tr[u].l].sz;if(klsz)utr[u].l;elseif(klsztr[u].cnt)returntr[u].val;else{k-lsztr[u].cnt;utr[u].r;}}return0;// 不会执行到这里因为保证有答案}intmain(){srand(time(0));// 初始化随机种子scanf(%d,n);rt0;while(n--){intop,x;scanf(%d%d,op,x);if(op1){// 插入 xintL,M,R;split(rt,x-1,L,R);split(R,x,M,R);// M 中为值等于 x 的节点if(M)tr[M].cnt,upd(M);elseMadd(x);rtmerge(merge(L,M),R);}elseif(op2){// 删除 xintL,M,R;split(rt,x-1,L,R);split(R,x,M,R);if(tr[M].cnt1)tr[M].cnt--,upd(M);elseM0;// 丢弃该节点rtmerge(merge(L,M),R);}elseif(op3){// 查询比 x 小的数的个数 1intL,R;split(rt,x-1,L,R);printf(%d\n,tr[L].sz1);rtmerge(L,R);}elseif(op4){// 查询第 x 小的数printf(%d\n,kth(rt,x));}elseif(op5){// 查询 x 的前驱intL,R;split(rt,x-1,L,R);intuL;while(tr[u].r)utr[u].r;// 左树的最大值printf(%d\n,tr[u].val);rtmerge(L,R);}elseif(op6){// 查询 x 的后继intL,R;split(rt,x,L,R);intuR;while(tr[u].l)utr[u].l;// 右树的最小值printf(%d\n,tr[u].val);rtmerge(L,R);}}return0;}功能分析操作描述实现方式时间复杂度1插入 x分裂成x、x、x增加重复次数或新建节点O(log n)2删除 x同上减少重复次数或丢弃节点O(log n)3查询比 x 小的个数 1分裂成x和≥x输出左子树大小 1O(log n)4查询第 k 小的数递归/循环根据子树大小查找O(log n)5查询 x 的前驱分裂成x和≥x在左子树中找最大值O(log n)6查询 x 的后继分裂成≤x和x在右子树中找最小值O(log n)空间复杂度O(n)最多存储 n 个节点每个插入操作最多新增一个节点。普通Treap vs FHQ Treap以本题为案例1. 核心操作实现操作普通Treap旋转版FHQ Treap分裂/合并版插入递归插入后通过旋转调整堆性质split成 ≤x 和 x再merge删除递归找到节点合并左右子树或降优先级后旋转split成 x、x、x减少计数或丢弃节点查排名递归根据大小累加split成 x 和 ≥x输出左子树大小1查第k小递归查找与普通Treap相同但不需要旋转前驱递归若当前≤x则往右否则往左split成 x 和 ≥x取左子树最大值后继递归若当前≥x则往左否则往右split成 ≤x 和 x取右子树最小值2. 代码复杂度普通Treap需要实现左旋、右旋插入/删除函数中旋转逻辑较复杂且删除操作通常要处理将节点旋转到叶子再删除代码量较多。FHQ Treap只需实现split和merge两个核心函数所有操作都基于它们逻辑清晰统一代码量少。代码更简洁不易出错。3. 性能时间常数两者均为 O(log n)但普通Treap的旋转操作涉及多次指针/索引修改常数略小FHQ Treap的split和merge每次操作会递归分裂或合并常数稍大但在 n ≤ 1e5 时差距可忽略。空间两者都是 O(n)每个节点存储左右儿子、值、优先级、大小、重复次数等基本相同。4. 扩展性特性普通TreapFHQ Treap区间操作如翻转难以实现需要维护懒标记且旋转会破坏区间结构天然支持可通过split按排名分裂打标记后合并可持久化需要复制节点并旋转实现复杂只需在split/merge时新建节点可轻松实现可持久化多重集需额外存储cnt或允许相同值节点同样用cnt处理且分裂策略明确≤x 与 x本题仅需基础操作两者均可胜任。但FHQ Treap的代码模式更通用稍加修改就能应对更复杂的问题如文艺平衡树、可持久化平衡树。5. 易调试性普通Treap旋转容易写错方向调试时需画图检查堆性质是否保持。FHQ Treapsplit和merge逻辑直观可以分段测试例如先测试split再测试merge且不需要处理旋转带来的父子关系错乱。调试更容易。6. 处理重复元素两者都可通过在节点中增加cnt计数来处理重复值。但普通Treap的删除操作如果采用合并左右子树的方法会丢失重复计数需特殊处理而FHQ Treap通过将相同值节点单独分离直接修改cnt即可逻辑更自然。7. 总结维度普通TreapFHQ Treap代码长度长短实现难度中等需理解旋转低只需 split/merge常数较小略大可接受可扩展性差难以区间操作/可持久化优秀天然支持区间和可持久化调试难度较高低更多系列知识请查看专栏《信奥赛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;}