线段树进阶（二）

势能线段树

势能线段树的时间复杂度基本都是基于“对节点的更新次数总共不会多于 $O(f(n))$ 次，而每次更新的复杂度是 $O(1)$ 的，所以总的更新复杂度不会超过 $O(f(n))$”，通常 $f(n)$ 都是 $O(n\log n)$ 量级的。

如何判断是否该使用势能对线段树的操作进行分析呢？通常来说，我们需要观察到某个量一定会越来越小、不可能通过操作越来越大、且到达最小之后不需要更新。比如说：

1. 开根号操作 $x\gets \lfloor\sqrt x\rfloor$（上取整和下取整都可以）。我们发现 $\sqrt x\le x$，当 $x\in [1,3]$ 的时候，这个根式
2. 对元素取最小值 $x\gets \min(x, v)$