无旋Treap，又称fhq_treap，是由范浩强大佬发明的一种高效数据结构。它在性能上兼具了Treap和Splay的特性，既比Treap易于学习，又比Splay在实际应用中表现出更高的效率。适合处理各种平衡树操作，包括插入、删除、搜索等，同时支持持久化操作（虽然本篇博客不涉及这部分内容）。它的树高期望大小为log级别，因此常数远小于Splay，适用于复杂数据结构和算法的优化。无旋Treap的核心思想是结合了树的二叉搜索树性质和堆的性质。在二叉搜索树的基础上，每个节点都被赋予了一个随机的优先级（权值）。这种随机性确保了树的结构在多次操作后能够保持平衡，从而使得操作复杂度的期望值为log级别。无旋Treap的两种基本操作是分裂(Split)和合并(Merge)。分裂操作将树分为两个子树，其中左子树的最大点权小于等于右子树的最小点权，操作的复杂度期望为log级别。合并操作则将两个子树合并成一棵，同样保证左子树的最大点权小于等于右子树的最小点权，通过随机选择节点作为根节点，可以确保树的平衡性。以下是基于无旋Treap的几种常见操作实现的示例代码。例如，插入节点时，首先创建新节点，然后根据权值将节点拆分成左右子树，之后使用Merge操作将左右子树与新节点合并。同样，删除节点的操作也是通过分裂操作来实现的。对于区间操作，可以通过分裂操作将目标区间表示的子树拆分出来，然后在根节点上进行标记，最后通过合并操作来完成操作。本文中还提供了几个实例问题的解决方案，如洛谷3369普通平衡树、洛谷3391文艺平衡树和洛谷3372线段树等问题，这些示例代码展示了如何利用无旋Treap进行插入、删除和区间操作，从而高效解决问题。对于学习和使用无旋Treap有兴趣的读者，推荐阅读相关资料，了解更深入的实现细节和优化技巧。同时，也可以在交流平台与作者互动，获取更多关于算法和数据结构的信息。为了便于学习，提供了一个PDF文件链接，以及作者的交流渠道和更多算法题解资源链接。