势能分析

这是原论文中证明的简化版本，但不失其正确性。

记 $\newcommand\mx{\text{mx}}\mx_x$ 为 $x$ 子树中最大值，$\newcommand\smx{\text{smx}}\smx_x$ 为 $x$ 子树中严格次大值，$\newcommand\fa{\operatorname{fa}}\fa(x)$ 为 $x$ 的父亲。称节点 $x$ 为关键点，当且仅当 $x$ 是根节点，或 $\mx_{\fa(x)}\neq \mx_x$。设变量 $\Phi$ 表示目前线段树上关键点个数。 （更多…）