Splay时间复杂度证明

高能预警! 需要前置知识“摊还分析”和“splay”

文章目录

前置小结论一些约定各种情形下势函数变化量zig/zagzig-zig/zag-zagzig-zag/zag-zig 单次splay（以及插入/删除等操作）的摊还代价闲得蛋疼---卡评测机

前置小结论

$\log x+\log y\le 2log(x+y)-2$ 容易看出这其实与$4xy\le (x+y{)}^2$等价，即与$(x-y{)}^2\ge 0$等价。

一些约定

对每个节点$x$，设其大小为$c(x)$（一个正数，此处取一即可），其子树的大小为$s(x)={\sum }_{u\in subtree(x)}c(u)$，这个节点对势函数的贡献为$\varphi (x)=\log s(x)$。 定义整棵树的势函数$\Phi (T)={\sum }_{x\in T}\varphi (x)$。显然$\Phi (T)>0$。

各种情形下势函数变化量

zig/zag

因为两种情况对称，所以图只画了$zig$情形

Y X' X C -> A Y' A B B C

$\begin{array}{rl}\Delta \Phi & =\varphi (X^{\prime })+\varphi (Y^{\prime })-\varphi (X)-\varphi (Y)\\ & =\varphi (Y^{\prime })-\varphi (X)\\ & \le \varphi (X^{\prime })-\varphi (X)\\ & \le 3(\varphi (X^{\prime })-\varphi (X))\end{array}$

zig-zig/zag-zag

图还是照例只画一种……

Z X' Y D A Y' X C -> B Z' A B C D

$\Delta \Phi =\varphi (Y^{\prime })+\varphi (Z^{\prime })-\varphi (X)-\varphi (Y)$ $$\begin{gathered} \because s(X)+s(Z^{\prime })=s(X^{\prime })-c(X^{\prime })<s(X^{\prime }) \\ \therefore \varphi (Z^{\prime })<2\varphi (X^{\prime })-2-\varphi (X) \\ \therefore \Delta \Phi <\varphi (X^{\prime })+(2\varphi (X^{\prime })-2-\varphi (X))-\varphi (X)-\varphi (X)=3(\varphi (X^{\prime })-\varphi (X))-2 \end{gathered}$$

zig-zag/zag-zig

画两张图？不存在的……

Z X' Y -> Y' Z' A X A B C D B C

$$\begin{gathered} \because s(Y^{\prime })+S(Z^{\prime })=s(X^{\prime })-c(X^{\prime })<s(X^{\prime }) \\ \begin{array}{rl}\therefore \Delta \Phi & =\varphi (Y^{\prime })+\varphi (Z^{\prime })-\varphi (X)-\varphi (Y)\\ & <(2\varphi (X^{\prime })-2)-\varphi (X)-\varphi (X)\\ & <3(\varphi (X^{\prime })-\varphi (X))-2\end{array} \end{gathered}$$

单次splay（以及插入/删除等操作）的摊还代价

对于操作$splay(x)$，把它拆成若干上述旋转，显然$\Delta \Phi <3\varphi (root)-dep(x)$。而单次操作的实际代价可表示成$k_i\ast dep(x)+c_i$。

所以，使用套路，将势函数乘上$k=\max \{k_i\}$，这样单次操作的摊还代价为$$\begin{gathered} \Delta \Phi +k_i\ast dep(x)+c_i \\ <3k\varphi (root)-k\ast dep(x)+k_i\ast dep(x)+c_i \\ =O(3k\log s(root))=O(\log s(root)) \end{gathered}$$

令$c_i=1$，设总结点数为$n$，得到最终摊还代价$O(\log n)$。自带一个$2\sim 3$的常数。

闲得蛋疼—卡评测机

实测$Luogu$模板文艺平衡树有$\%50$的数据满足总旋转次数$\le 2.6\times n\log n$ 有$\%100$的数据满足总旋转次数$\le 2.73\times n\log n$