神仙p_b_p_b发现了一种神奇的分块思路，然后发现给别人造了轮子。
给你一个长度为 $n$ 的序列 $\left\langle a _i\right\rangle^{n} _{i=1}$和一个满足结合律的运算 $\circ$ 。Sqrt Tree可以在 $O(n \log_2\log_2n)$ 的时间内预处理，并在 $O(1)$ 的时间回答计算 $a _l\circ a _{l+1}\circ\cdots\circ a _r$ 的询问。
做法描述
无论如何先分块
首先给原序列分块，块大小 $\sqrt{n}$ 。对于每个块，计算：
- $P_i$ 块内的前缀询问答案
- $S_i$ 块内的后缀询问答案
再维护一个额外的数组 $\left\langle B_{i,j}\right\rangle$ 表示第 $i$ 个块到第 $j$ 个块的答案。
预处理上述的值可以在 $O(n)$ 时间与空间内完成。然后我们就可以在 $O(1)$ 时间内回答跨块的询问。然而对于整个区间都在块内部的询问需要 $O(\sqrt{n})$ 的时间才能回答。
构建一棵树
可以在每个块内递归地构造上述结构来支持块内的查询。此时我们相当于建出一棵树，每个节点代表序列的一个区间。由于大小为 $k$ 的结点有 $O(\sqrt{k})$ 个子节点，于是整棵树的高度是 $O(\log_2\log_2n)$ 的。而每一层的区间总长为 $n$ ，因此建树的复杂度是 $O(n\log_2\log_2n)$ 的。
于是我们可以在 $O(\log _2\log _2n)$ 时间内回答询问。只需要找到一个区间长度最小的结点使得其能包含询问区间 $[ l,r ]$ ，这样 $[ l,r ]$ 在 $u$ 的分块区间中一定是跨块的，就可以 $O(1)$ 计算答案了。所以查询一次复杂度相当于树 $O(\log _2\log _2n)$ 。然而还能继续优化此过程。
优化询问
可以二分高度，再 $O(1)$ 判断合不合法。这样复杂度就被优化到 $O(\log _2\log _2\log _2n)$ 。然而我们希望能够优化到 $O(1)$ 。
我们假设
- 每一个块的大小都是 $2$ 的整数幂次；
- 相同层的块大小相同。
此时可以将原序列补成 $2$ 的幂次，预处理复杂度不变。
现在可以快速确定一个区间是否在同一个块中了。令序列的下标从 $0$ 开始，可以发现，一个大小为 $2^k$ 的块内，元素的下标（二进制表示）仅有后 $k$ 位不同。所以，对于询问区间 $[l,r]$ ，计算 $l\ \operatorname{xor}\ r$ 的最高位的 $1$ 就可以快速确定答案区间所在的层。
如此就可以在 $O(1)$ 时间内回答询问。
单点修改
Sqrt Tree 支持单点修改。
朴素实现
考虑长度为 $len$ 的结点中储存的信息（分块后的前缀询问数组 $P_i$ ，后缀询问数组 $S_i$ ，块间询问数组 $B_{i,j}$），可得 $P_i$ 及 $S_i$ 中都只有 $O(\sqrt{l})$ 个元素改变，而 $B_{i,j}$ 中有 $O(l)$ 个元素改变。因此，朴素地在Sqrt Tree上修改的时间复杂度是 $O(n+\sqrt{n}+\sqrt{\sqrt{n}}+\cdots)=O(n)$ 。
使用 Sqrt Tree 替代 B 数组
发现复杂度瓶颈在于更新根节点的 $\left\langle B_{i,j}\right\rangle$ 。注意到 $\left\langle B_{i,j}\right\rangle$ 的作用：表示块 $i$ 到块 $j$ 的答案。把根节点分的每个块当做一个序列，在块上再开一棵 Sqrt Tree，称作 $\text{index}$ ，长度为 $O(\sqrt{n})$ 。此时，它就可以用来充当原树根节点上的 $\left\langle B_{i,j}\right\rangle$ 的作用了，而其他非根节点仍使用 $\left\langle B_{i,j}\right\rangle$ 来维护。
所以我们可以先 $O(\sqrt{n})$ 地更新原树上的结点（根节点只更新 $P_i$ 与 $S_i$），再对 $\text{index}$ 进行更新。由于 $\text{index}$ 也是单点更新（原序列单点修改只影响一个块的答案），需要 $O(\sqrt{n})$ 的时间。所以单点修改需要 $O(\sqrt{n})$ 。
同时仍能保证询问能在 $O(1)$ 时间内回答（即使调用 $\text{index}$ 也只会调用一次）。
参考代码
鸽了。