吉司机线段树（Segment Tree Beats!）复杂度分析

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

记 $\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$ 表示目前线段树上关键点个数。

不难说明，$\smx_x$ 是 $\mx_y$ 的最大值，其中 $y$ 取遍 $x$ 的子树（不含它自身）中所有关键点。那么，我们对区间 $[l,r]$ 取 $a_i\leftarrow \min\{a_i,c\}$，在线段树上 DFS 暴力更新节点信息时，递归访问 $x$ 子树的充分必要条件就变成“$x$ 所辖区间是 $[l,r]$ 子区间，且 $x$ 的子树（不含它自身）中存在至少一个关键点 $y$，满足 $\mx_y\geq c$”。而 DFS 遍历过的所有节点 $y$，在此后都将满足 $\mx_y=c$，变成非关键点。故设 DFS 过程中访问（并消除）了 $k$ 个关键点，我们至少访问了这 $k$ 个关键点到 DFS 起始节点的路径并，节点总数为 $\newcommand\bigO{\operatorname{O}}\bigO(k\log n)$（由 $k+k/2+k/4+\cdots\leq 2k$，当 $k$ 足够大时，复杂度为 $\operatorname{o}(k)$）；而由上文可得，我们不会递归路径并以外节点的子树。故而我们以 $\bigO(k\log n)$ 的时间使得 $\Phi$ 减少了 $k$。

所以当 $\Phi$ 的总变化次数为 $m$ 时，总时间复杂度为 $\bigO(m\log n)$。若不带修改，则 $m\leq n$，总复杂度为 $\bigO(n\log n)$；大多数类型的单点修改会使得 $\Phi\leftarrow\Phi+\bigO(\log n)$，故总复杂度为 $\bigO(n\log^2 n)$。