吉司机线段树(A.K.A. 势能线段树),个人觉得,就是对普通线段树的一种优化技巧。这种优化技巧有点像搜索算法里面的剪枝。
在普通线段树中,为了避免一次区间操作浪费太多时间,我们利用了一种叫作懒标记(Lazy Tag
)的技巧。懒标记的核心是利用操作的可合并性,当进行操作时,先在根节点上进行标记,需要访问子节点时再把标记下放。
但是,对于一些没有可合并性的操作(比如开平方等),懒标记就不适用了。
但是,既然题目出出来了,就应该有方法解,这类型的题目的操作大多有一个共同点:操作次数比较有限。
比如 开平方并向下取整 操作,哪怕是一个很大的数,通过有限次操作( 64 64 64 位正整数好像最多只需要 25 25 25 次吧,不记得了)就可以使它变成 1 1 1,然后操作就失效了(再操作也还是 1 1 1)。
我们可以想象有这些数本身就有一定的某种“势能”,而每次操作都会使得这个“势能”降低,知道达到最低(即使操作失效)。
我们可以记录下这个“势能”,然后进行区间修改时,先判断这个区间的最高“势能”是否已经达到了最低,如果是,那么这个操作对于这个区间而言就失效了,可以退出操作。
如果“势能”下降的速度足够开,就可以使时间复杂度降低到可以承受的范围。
比如对于那个 开平方并向下取整 的操作来说,我们就记录下每个区间的最大值,如果某个区间的最大值已经是 1 1 1 了,那么进行操作时就可以忽视这个区间。
[Problem] \color{blue}{\texttt{[Problem]}} [Problem]
给定长度为 n n n 的数列 a 1.. n a_{1 .. n} a1..n,三种操作:
lowbit
highbit
[Analysis] \color{blue}{\texttt{[Analysis]}} [Analysis]
不是很显然的,我们知道,操作 2 2 2 会使每个数二进制下 1 1 1 的个数减少 1 1 1,而操作 3 3 3 不会影响每个数二进制下 1 1 1 的个数。
于是可以使用吉司机线段树,“势能”就是每个数二进制下 1 1 1