2022.08.21 吉司机线段树略讲

$$\text{Interpretation}$$

吉司机线段树（A.K.A. 势能线段树），个人觉得，就是对普通线段树的一种优化技巧。这种优化技巧有点像搜索算法里面的剪枝。

在普通线段树中，为了避免一次区间操作浪费太多时间，我们利用了一种叫作懒标记（Lazy Tag）的技巧。懒标记的核心是利用操作的可合并性，当进行操作时，先在根节点上进行标记，需要访问子节点时再把标记下放。

但是，对于一些没有可合并性的操作（比如开平方等），懒标记就不适用了。

但是，既然题目出出来了，就应该有方法解，这类型的题目的操作大多有一个共同点：操作次数比较有限。

比如 开平方并向下取整 操作，哪怕是一个很大的数，通过有限次操作（$64$ 位正整数好像最多只需要 $25$ 次吧，不记得了）就可以使它变成 $1$，然后操作就失效了（再操作也还是 $1$）。

我们可以想象有这些数本身就有一定的某种“势能”，而每次操作都会使得这个“势能”降低，知道达到最低（即使操作失效）。

我们可以记录下这个“势能”，然后进行区间修改时，先判断这个区间的最高“势能”是否已经达到了最低，如果是，那么这个操作对于这个区间而言就失效了，可以退出操作。

如果“势能”下降的速度足够开，就可以使时间复杂度降低到可以承受的范围。

比如对于那个 开平方并向下取整 的操作来说，我们就记录下每个区间的最大值，如果某个区间的最大值已经是 $1$ 了，那么进行操作时就可以忽视这个区间。

$$\text{Example - Hdu 7059}$$

$\text{[Problem]}$

给定长度为 $n$ 的数列 $a_{\mathrm{1..}n}$，三种操作：

1. 求区间和
2. 将区间内的所有数减去它的 lowbit
3. 将区间内的所有数加上它的 highbit

$\text{[Analysis]}$

不是很显然的，我们知道，操作 $2$ 会使每个数二进制下 $1$ 的个数减少 $1$，而操作 $3$ 不会影响每个数二进制下 $1$ 的个数。

于是可以使用吉司机线段树，“势能”就是每个数二进制下 $1$