水群时看到了，记一下。

预处理 O(n)，查询期望 O(1) 做法

形式地，设查询的信息构成半群（对运算封闭且满足结合律）。

分块，将信息分成 块，则每块长度为 。

考虑暴力处理每块的前缀、后缀答案，暴力处理每个整块间的答案，取 ，预处理复杂度是 的。

现在，对于跨越整块的询问，我们可以 查询，但是，对于块内的询问，我们只能暴力查询。

不过，块内询问出现的概率为 ，单次询问的复杂度为 ，因此期望下复杂度是 的。

即使有毒瘤出题人试图卡掉这种做法，先不提是否存在替代方案，我们可以微调块长，使得难以构造大量块内查询，因为这类数据可能让暴力通过。

预处理 O(n log log n)，查询严格 O(1) 做法

保持上文中的假设，在处理块内查询时，我们考虑在块上递归地建成上文中的结构。

由于每块的块长是原长的 ，递归深度不会超过 。因此预处理的时空间复杂度均为 的。

同理，单次查询时的复杂度是最劣 的（但是显然，在询问随机的情况下，期望复杂度仍为 ）。

如果你追求更快的查询，可以考虑类似倍增求 LCA 的方法，做到单次 。

更进一步地，可以使用类似猫树地处理手段，将长度补齐到 ，显然这最多使长度翻倍，因此长度仍是 的。此时我们可以使用位运算和一些内置函数加快查询，做到最劣单次 。

我们继续这种思路，考虑如何支持修改，考虑不再暴力预处理整块间的查询，而是将上文中结构建在整块查询上，这样我们就得到一个 单次修改的算法。