一种期望线性的静态区间查询

水群时看到了，记一下。

形式地，设查询的信息构成半群。

分块，将信息分成 \(B\) 块，则每块长度为 \(\dfrac{n}{B}\)。

考虑暴力处理每块的前缀、后缀答案，暴力处理每个整块间的答案，取 \(B=O(\sqrt{n})\)，预处理复杂度是 \(O(n)\) 的。

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

不过，块内询问出现的概率为 \(O(\dfrac{1}{B})\)，单次询问的复杂度为 \(O(B)\)，因此期望下复杂度是 \(O(1)\) 的。

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