FHQtreap

原发布于我的个人博客 前言 FHQtreap绝对是平衡树里最好写，最实用的，他几乎能做所有splay或其它平衡树能做的事，还能可持久化！ 这篇文章将会介绍FHQtreap的基本操作和维护区间的操作，并附上例题。 基本操作 FHQtreap的基本操作只有两个，分裂和合并。 有些读者可能会问，分裂和合并 ......

引入 无旋转 $treap$ ，又称分裂合并树，因为其操作由分裂合并实现，代码简单，好调，并且没有旋转操作，可能有时常数略大，但不影响其优秀。 原理 $fhqtreap$ 是以 $BST$ 二叉搜索树为基础实现的 不同于 $BST$ 的是，加入数值时我们保存一个随机 $key$ 值 ，并保证父亲的 ......

1.基本操作：split（分离）和merge(合并) 一系列操作，如修改元素，删除元素，查找前缀后缀都通过这两个基本操作实现。 split的作用是把一颗树根据某个限制（比如模板题中是根据节点的权值划分） 2.有两种fhqtreap.一种维护集合（普通平衡树），一种维护数组(文艺平衡树) 注意fhqt ......