本题分块做法查询为 $\Theta(1)$，修改为 $\sqrt n$，时间近似线段树，并且空间更小。