屎一样的一年还有两天就过去了呢。
感觉都阳了一周了还是没有回复到正常状态，真的挺讨厌的。今天随便找了篇论文假学习了一会儿。
由于懒，所以大量内容属摘抄。
平衡树的 finger search
1 Splay
2 Treap
2.1 节点深度
\[1+\sum_{i=1}^{x-1}\frac{1}{x-i}+\sum_{i=x+1}^{n}\frac{1}{i-x}=O(\log n) \]3 Finger Search
记 \(d(x,y)\) 表示两个元素 \(x,y\) 在集合中的排名之差。
下说明 \(\mathbf{finger search}\) 的复杂度为 \(polyd(x,y)\)。
3.1 Splay 上的 Finger Search
定理 3.1 (Dynamic Finger Theorem). 在一棵 \(n\) 个节点上的 Splay 上进行 \(m\) 次的插入、删除或
者查找操作的总时间为 \(O(n+m+\sum_{i=1}^{m}\log(d_i+1)\)。其中 \(d_i\) 表示第 \(i\) 次操作的元素与第 \(i−1\) 次操作的元素在该操作时的排名之差。第 \(0\) 次操作的元素可以视为初始的根节点。