美食殿堂

所爱隔山海,山海亦须平

Splay 学习笔记

势能仅仅是一个调蓄的工具,所以常数的忽略必须和时间开销统一。

zig 和 zag 时间开销加势能变化量等于两个结点势能差加一。

zig-zig 和 zig-zag 时间开销加势能变化量等于两个结点势能差。

一次 splay 时间开销加势能变化量最多等于最终位置初始位置势能差加一,因为可能多出一次 zig 或 zag。

$m$ 次 splay 时间开销加势能总变化量最多等于 $m\log n$。

根据势能函数的定义,势能差必然为正,但由于时间开销的存在,势能变化量可正可负,势能总变化量也可正可负。而势能总变化量的绝对值最多等于 $n\log n$,所以总时间开销最多等于 $(m+n)\log n$。


每次查询后旋转到根,就仅仅是增加了常数。

插入和删除操作最多带来 $\log n$ 的势能变化量,不会影响时间复杂度。


为了方便把操作的区间夹在根的右子树的左子树,我们一般在 Splay 初始化时插入 $\infty$ 和 $-\infty$。

对于 Splay,我习惯于在 pushdown 时才更新当前结点的某些信息,所以我就在 pushup 中先 pushdown 左右儿子。

维护序列时,因为不存在的儿子用 $0$ 表示,所以不进行判断会出问题。拿最大子段和不能选空的情况作为例子,具体地,我们有以下解决方法:

  • $0$ 的最大子段和置为 $-\infty$,避免选空。
  • 最两侧结点(即初始化插入的两个)的值置为 $-\infty$,避免单独被选成最大子段和。
  • 有了 $0$ 的特殊性,所以不能对它 pushdown 或者 pushup,在一些地方要注意一下。

原论文

部分结论摘要:

  • Splay 是 Dynamic Finger Search Tree,访问的均摊时间复杂度为 $O(\log d(finger_{i-1},finger_i))$,其中 $d$ 表示排名之差。
  • 合并两棵大小分别为 $n,m(n\leq m)$ 的 Dynamic Finger Search Tree 的时间复杂度为 $O(n\log\frac{m}{n})$。具体合并方法为将较小树中元素从小到大或从大到小加入较大树。
  • 按任意顺序将 $n$ 个元素合并成一棵 Dynamic Finger Search Tree 的时间复杂度为 $O(n\log n)$。除了归纳证明外我们还可以考虑每个元素合并时被加入的贡献 $O(\sum_{i=2}^k\frac{s_i}{s_{i-1}})=O(\log n)$,其中 $s_{i-1}$ 和 $s_i$ 表示该元素在第 $i-1$ 次被加入时较小和较大树的大小。

加入分裂一个区间的操作,仍然最多带来 $\log n$ 的势能变化量。

但合并时暴力加入会导致时间复杂度变成 $O(nm)$。不妨每次判断当前极值是否存在,存在就直接加入,否则就分裂出一棵可以直接插入的子树插入。用每个元素和相邻元素差的对数作为势能函数,如果一个间隔在合并的时候被分裂开,肯定有一边与相邻元素的差减半。这样至少是 $O((m+n)\log^2 n)$ 的,不知道用 Finger Search 分析能否更优。