nexthexonextbutterflyvolantisyearnyiliashokaindigoapollolandscapecactusmateryicarusfluidmaterial 笛卡尔树 这个笛卡尔树没写出来，气死了 他是二叉树，他是堆，二叉树中序遍历的结果就是数组a 笛卡尔树的构造 先看一个简单的笛卡尔树 我们使用增量构建笛卡尔树来完成，就和增量构建后缀自动机一样容易...

nexthexonextbutterflyvolantisyearnyiliashokaindigoapollolandscapecactusmateryicarusfluidmaterial Y快速前缀树 继X快速前缀树以后，Dan Willard又提出了X快速前缀树的改进版本 改进X快速前缀树 我们还是继续考虑n个小于M的整数(n<M)，我们按照大小，从小到大分组,每组的元素的个...

nexthexonextbutterflyvolantisyearnyiliashokaindigoapollolandscapecactusmateryicarusfluidmaterial X快速前缀树 我以前就说过，当你的数据结构达到了一定的基础，就可以学习那些更加高级的数据结构了，往往那些更加高级的数据结构由基本数据结构组合而成。 先提出一个问题 现在要你维护一个多重集合，支持3种...

nexthexonextbutterflyvolantisyearnyiliashokaindigoapollolandscapecactusmateryicarusfluidmaterial ternary search tree字典树的缺点 不难想到，对于那些字符集特别大的字典树来说，他们的空间消耗特别大，因为每个节点都要储存大量的指针，而这些指针往往又是空的。 将BST与trie结合...

nexthexonextbutterflyvolantisyearnyiliashokaindigoapollolandscapecactusmateryicarusfluidmaterial # cartesian tree 笛卡尔树是一颗二叉树，他满足中序遍历为维护的序列，且满足堆的性质 build我们使用单调栈来维护树根到叶子的链，在单调栈的构建中完成树的构建 ct代码

nexthexonextbutterflyvolantisyearnyiliashokaindigoapollolandscapecactusmateryicarusfluidmaterial vantate point treevp tree 是一颗二叉树，他和kd tree有着一定的相似度, 树上信息每一颗子树都要维护一个点集，对于每个节点，我们都维护一个距离d，然后将到该节点的距离小...

nexthexonextbutterflyvolantisyearnyiliashokaindigoapollolandscapecactusmateryicarusfluidmaterial # scapegoat Tree 替罪羊树，他是一个暴力的bst，与普通bst相比，他记录了子树的大小，用参数alpha来定义平衡，即左右子树的大小都不允许超过根的alpha倍，所以往往aplha是...

nexthexonextbutterflyvolantisyearnyiliashokaindigoapollolandscapecactusmateryicarusfluidmaterial namedescirption inputoutputsample inputsample outputtoturialcode

nexthexonextbutterflyvolantisyearnyiliashokaindigoapollolandscapecactusmateryicarusfluidmaterial Treap 树堆Treap来源于Tree+Heap的组合, 其实就是一棵树，他的节点储存了两个键，一个是我们维护的信息，另外一个是随机数，我们不妨设前者叫key，后者叫rand_key，Treap的...

nexthexonextbutterflyvolantisyearnyiliashokaindigoapollolandscapecactusmateryicarusfluidmaterial # splay tree 伸展树，以其操作splay出名。 伸展树的本质就是bst， ## splay操作 伸展树对splay操作的参数是一个节点，他的结果是将这个节点通过双旋变成根。 ## s...