设 $w(x)$ 为 $x$ 的子树大小的对数。

初始势能：$\varphi(0)=\sum \log_{2}(sz(x))\le\sum\log_{2}n=n\log_{2}n$。

一下假设 $x$ 为 rotate 的点，$p$ 为 father，$g$ 为祖先。

1、Zig 操作

时间：$\Theta(1)$

显然有 $w'(x)=w(p)$（自己画个图就知道了）。

势能变化：$\Delta_{\varphi_{Zig}}=w'(x)-w'(p)-w(x)-w(p)\le w'(p)-w(x)$。

2、Zig-Zag 操作

时间：$\Theta(1)$。

势能变化：$\Delta_{\varphi_{Zig-Zag}}=w'(x)+w'(p)+w'(g)-w(x)-w(p)-w(g)=w'(x)+w'(g)-w(x)-w(p)\le w'(p)+w'(g)-2w(x)$。

如果 $sz(p)\ge sz(g)$，有 $2sz'(g)\le sz(x)\Rightarrow 1+w'(g)\le w'(x)$。

如果 $sz(p)<sz(g)$，有 $2sz'(p)\le sz'(x)\Rightarrow 1+w'(p)\le w'(x)$。

有 $w'(p)<w'(x),w'(q)<w'(x)$ 代入可得 $\Delta_{\varphi_{Zig-Zag}}\le2w'(x)-w(x)-1$。

假设一共执行 $k$ 次操作，那么 $\hat c=c+\Delta\phi=\sum2w'(x)-w(x)+\Theta(k)-\Theta(k)=\sum w'(x)-w(x)$。

3、Zig-Zig 操作

时间：$\Theta(1)$

势能变化：$\Theta_{\varphi_{Zig-Zig}}=t_{Zig-Zig}+w'(x)+w'(p)+w'(g)-w(x)-w(p)-w(g)=w'(p)+w'(g)-w(x)-w(p)\le w'(x)+w'(g)-2w(x)\le 2(w'(x)-w(x))$。

由于一次 Splay 操作中可能多次进行 Zig-Zag 操作，为了摊还实际代价，需存在常数 $-1$。qwq

$sz'(x)=sz(A)+1+SZ(B)+1+sz(C)+1+sz(D)+1+2=sz(x)+sz'(g)+2$。

因此 $2w'(x)-w'(g)-w(x)=\log_{2}(\frac{sz(x)^2}{sz(x)sz(g)})=\log_{2}(\frac{(sz(g)+sz(x)+2)^2}{sz(x)sz(g)})\le \log_{2}(\frac{2sz(x)sz(g)}{sz(x)sz(g)})=1$。

所以 $\Delta_{Zig-Zig}\le 3(w'(x)-w(x))-1$。

假设有 $k$ 次操作，$\hat c=c+\Delta\phi=\Theta(k)+\sum w'(x)-w(x)-\Theta(k)=\sum w'(x)-w(x)$。

得证。

转载自 RSY 的博客：(Splay 时间复杂度证明（势能分析）)[https://www.luogu.com.cn/blog/123456--abcdef/splay-shi-jian-fu-za-du-zheng-ming-shi-neng-fen-xi-post]