RainAir
My OI Blog
RainAir


文章归档

左偏树学习笔记

定义 大家都知道优先队列吧。 有时候我们需要合并优先队列,反正我们不能重新插入吧,我们就需要一种神奇的数据结构--可并堆 可并堆可以支持在$O(NlogN)$下进行插入,删除,合并,求极值。 在OI选手中,实现可并堆的最好方法是左偏树 那么左偏树是递归定义的,…

   110   2018-05-19 去围观

平衡树学习笔记

定义 什么叫平衡树?就是看起来很平衡的树。 它是一种中序遍历有序的一棵搜索树,满足左儿子的权值<自身权值<右儿子的权值 它是递归定义的。 算法 目前平衡树的算法很多,在OI中,我们常使用Treap和Splay<(set) 平衡的概念有高度平衡,重量平衡等。 …

   221   2018-05-02 去围观
文章归档