Treap

[mathjax]

\(\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范爷)”

树链剖分

将树上的点按照一定方式分为许多条链,从而将在树上的区间操作转移到线性数据结构上,减少时间复杂度的同时维护许多有用的信息。

常用的剖分依据有重链剖分,实链剖分(Link-Cut Tree)等。一般称重链剖分为树链剖分。

继续阅读“树链剖分”

最小费用最大流和Edmonds-Karp算法

为流量网络中的每一条边赋予一个单位流量代价,在求最大流的基础上求最小代价的问题称为最小费用最大流问题(一般也称为费用流问题)。

求最大流的Edmonds-Karp算法通过广度优先搜索寻找增广路。
求费用流时,将广搜改为SPFA,求一条总单位开销最小的增广路,这样就可以保证方案总开销最小的同时流量最大。

继续阅读“最小费用最大流和Edmonds-Karp算法”