势能仅仅是一个调蓄的工具,所以常数的忽略必须和时间开销统一。
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 分析能否更优。