FHQ Treap

\(\text{FHQ Treap}\)是一种好写好用的平衡树。

它的平衡策略和普通\(\text{Treap}\)相似,采用在维护\(\text{BST}\)性质的同时维护随机的堆的形态来维持平衡;
但是维护结构的方式和\(\text{Treap}\)不同,不采用旋转,而是采用拆和合并的方法来维持树和堆的特性。

同时,由于\(\text{FHQ Treap}\)的操作所涉及的节点和基于旋转的其他平衡树相比少(仅\(\log n\)个),它支持可持久化

继续阅读“FHQ Treap”

Treap

\(\text{Treap}\)是一种通过维护堆和二叉搜索树两重性质来限制树高的平衡树。

每一个节点都被赋予了两个值,称作\(val\)和\(key\),分别按照BST和堆的性质维护:

  • 小根堆:每一个节点的\(key\)都小于等于他的两个子节点的\(key\)
  • 二叉树:每一个节点的\(key\)都比他左子的\(val\)大,比右子的\(val\)小

每一个节点的\(key\)是随机指定的,这样可以保证期望树高为\(\log n\)

继续阅读“Treap”

后缀自动机与线性构造后缀树——转自fanhq666(fhq范爷)

转自范爷的blog:http://fanhq666.blog.163.com/blog/static/8194342620123352232937/
原始文件:https://blog.edgaru089.ml/custom-items/后缀自动机与线性构造后缀树.txt

冬令营上我犯了最大的一个错误,就是在陈立杰讲后缀自动机的时候睡觉。
这导致了,我在冬令营之后只能花费好几个不眠之夜来思考后缀自动机到底是什么。
突然,在某天的梦里,我看到了一幅神奇的图景,我突然发现,一切都是那么的明晰了。

继续阅读“后缀自动机与线性构造后缀树——转自fanhq666(fhq范爷)”