【转载】史上最简单的平衡树——Treapwithoutrotation作者：fzszkl博客地址：https://ac.nowcoder.com/discu...使用本PDF文件时请保留以上信息！谢谢您的合作！我觉得文章不错请点击链接为博客点赞！高能预警：所有示例代码均为数组版，欢迎复制！前置知识：线段树！请确保您完全理解最基本的线段树和LazyTag（区间加法和区间求和）.1。SpinlessTreap，又名fhq_treap，是范浩发明的一种强大的数据结构。总的来说，它可以支持Treap和Splay等平衡树的所有操作，支持持久化（不过这篇博客就不讲了），常数比Splay小很多，但是在处理LCT问题上略逊于Splay，以至于我还不知道。对于初学者来说，比Splay好学，比Treap好用，真是性价比极高的数据结构。二、详解首先，让我们回顾一下平衡树的鼻祖——二叉搜索树的本质：递归定义，空树为二叉搜索树，二叉搜索树的左子树的最大点权值根小于右子树的最小点权，二叉搜索树的左右子树也都是二叉搜索树。二叉搜索树的插入、删除、查找操作很容易被极端数据卡充满复杂性。这时候我们就需要各种神奇的操作来保证它的树高预期在日志级别。直接看spin-freeTreap是怎么操作的（因为我对其他类型了解不多）：free-freeTreap有两个基本操作：(1)SplitSplit将树分成两棵树，其中最大点权重树A的点权值小于等于树B的最小点权值。因为树的高度期望是log，所以单次操作的复杂度期望是log。(2)Merge将两棵树合并为一棵树，其中树A的最大点权值小于或等于树B的最小点权值。为了保证树高期望为log，我们要找到一个随机合并的方式。不（他妈的你什么都没说）。好吧，为了博客的复习，再详细说说吧。下面的示例代码中，0代表一个空节点，Pushdown代表下载标记，Pushup代表向上更新。先来看一下Split:voidSplit(intNod,intSiz,int&A,int&B){if(Nod==0)return(void)(A=B=0);下推（点头）；if(Siz<=Size[Ls[Nod]])B=Nod,Split(Ls[Nod]d],Siz,A,Ls[点头]);elseA=Nod,Split(Rs[Nod],Siz-Size[Ls[Nod]]-1,Rs[Nod],B);俯卧撑（点头）；}nod是当前要拆的节点，A和B是指向左右子树的根节点的指针，siz是拆分后的左子树的大小。翻译成大人的话：当分裂的大小不超过左子树的大小时，会将当前节点分配给右子树（B=Nod），然后进入左子树进行分裂，分裂后的左子树仍然会传递给A，被移除的右子树将作为当前节点Tree的左子树，否则相同。首先确保你对指针有一个初步的了解（因为我只是初步了解），然后确保你牢记二叉搜索树的本质（这样你就可以理解为什么要这样拆分它，不无论如何Points都不能改变节点从小到大的排序规律）。如果按照重量拆分Split，稍微改一下就可以了。然后看一下Merge：intMerge(intA,intB){if(A==0orB==0)returnA|乙;注册intAns；下推(A);下推(B);if(Pos[A]>Pos[B])Rs[A]=Merge(Rs[A],B),Ans=A;elseLs[B]=Merge(A,Ls[B]),Ans=B;俯卧撑（答案）；returnAns;}Pos是一个随机权重，所以我们可以保证树的高度期望是log(魔芋：因为形成长度为n的链的概率大约是$\frac{1}{2^n}$乘以组合号码或其他东西）。这两种合并方法是等价的。两个节点中的一个作为这一步的根节点，另一个节点递归地与根节点的子树合并。请再回忆一下二叉搜索树的本质，所以一定要保证A在B的“左边”。一定要注意，Merge(A,B)和Merge(B,A)是很不一样的！有了这两个看似特别nb的操作，结合起来我们可以做很多nb的事情~常规操作查排名，查前驱后继等操作，和普通的平衡树一样，只是在树上dfs。但是为了体现unrotatedTreap的优越性，下面给出的示例代码使用了两个基本操作优点是直观易写。缺点是常数比直接dfs略大。插入一个节点创建一个新节点，然后根据权重拆分成左右子树，然后Merge(Merge(left,newnode),right)就可以了。删除的节点根据权值分为左右子树和要删除的节点，然后直接Merge(left,right)就可以了。一般来说，区间操作就是通过Split把你需要操作的区间所代表的子树剪掉，然后标记根节点，然后合并。3.喜闻乐见的小例子（一）洛谷3369普通平衡树：https://www.luogu.org/problem...需要支持插入、删除、元素校验Ranking和Ranking元素，查前辈和继任者。模板题，除了区间操作，实现上面的东西就可以了。AC码：https://www.luogu.org/recordn...启用O2优化，洛谷更新数据最后262ms（二）洛谷3391文学平衡树：https://www.luogu.org/problem...A从1到N的排列，M次操作，每次翻转一个区间，求出最终的排列。仅使用实现区间操作即可，如何标注，请参考下载标注代码。AC代码：https://www.luogu.org/recordn...开启O2优化，洛谷更新数据后488ms（3）洛谷3372线段树：https://www.luogu.org/problem...区间加法，区间求和。这个例子是为了方便大家理解LazyTag，从线段树到平衡树，或者普通平衡树到区间平衡树我特意重写了这段代码。是不是超级良心啊~AC代码：https://www.luogu.org/recordn...开启O2优化，为什么最水的代码在罗谷更新数据后642ms反而是最慢的，而且新数据太强大了。四、什么是售后保障？博客太烂看不懂？推荐阅读：http://iwo.im/?q=%E6%97%A0%E6。..(↑↑↑看完一定会回来喜欢的。)本文PDF文件：链接：https://pan.baidu.com/s/1vR9d...提取码：mnc4仅供学习和沟通！！！谢谢您的合作！！！
