令块长为 $B$，通过操作分块可以得到一个 $\mathcal O(Bn\log n+\frac{q^2}{B}\log n)$ 的做法。两只 $\log$ 分别来自重构的基于 BIT 和块内修改的贡献需要倍增求 $k$ 级祖先。和这篇题解的第一个做法是一样的。

这个做法确实非常卡，我卡了一个多小时。下面是一些警示后人的方法：

1. 把块长改成 $\sqrt {q(1+\log q)}$，不知道为什么反正就是很快。
2. 把重构改成不递归的版本，实测快了非常多。
3. 减少树状数组的修改次数。
4. 可以把 $n^{-1}$ 之类的常数提出来，不用乘那么多次。
5. 实在不行就把 $k$ 级祖先改成长剖。