修改操作时每次 $x\leftarrow x+lowbit(x)$ 会使得 $lowbit(x)$ 至少增加 $1$。
询问操作时每次 $x\leftarrow x-lowbit(x)$ 也会使得 $lowbit(x)$ 至少增加 $1$。
by Kubic @ 2022-03-28 22:42:20
@[Kubic](/user/119621) 我觉得楼主是在问如何证明单点加区间和复杂度至少为 log 级
by FerventTemp0 @ 2022-03-28 22:48:38
哦，那我好像理解错了
by Kubic @ 2022-03-28 22:51:49
但你这个问题就变得模糊不清了，因为存在许多复杂度倾斜向询问或者倾斜向修改的做法。
by Kubic @ 2022-03-28 22:53:15
应该是有的，但可惜我不搞计算机。。
by 樱初音斗橡皮 @ 2022-03-29 00:51:38
@[StillEmpty](/user/150956) 我问了某个搞计算机的大佬，其说在线是有下界的
by 樱初音斗橡皮 @ 2022-03-29 07:58:13
@[樱初音斗橡皮](/user/66287) 所以无法证明离线算法中没有比 $m \log n$ 更快的？
by StillEmpty @ 2022-03-29 08:02:50
似乎我只见过算法导论上出现的那些问题的复杂度下界证明
by StillEmpty @ 2022-03-29 08:03:35