可以考虑分两层块，时间复杂度为 $O(nB_2+\frac{n^2}{B_1^2}+\frac{nB_1}{B_2^2})$，取 $B_1=n^{\frac{6}{7}},B_2=n^{\frac{2}{7}}$，可以做到 $O(n^{\frac{7}{8}})$，虽然比 Sqrt Tree 略劣，但是查询时 $O(1)$ 的。适用数据范围：$n\le10^7,q\le10^8$，用某种特殊方式生成询问（否则输入寄了）。

常数应该是比 Sqrt Tree 小的吧