轻量级带修 ST 表！

upd 2024.11.12: 被 zkw 偏序了，现在这个东西完全没用了。/ng

upd 2025.2.15 听说了一个看起来很有道理的多层分块，有空写一下。

在 LA 看到的。

注意到 ST 表上，单点修改只会影响 $O(n)$ 个位置的值。

考虑类似 sqrt tree 的结构：对序列以 $O(\sqrt n)$ 块长分块，块内维护前后缀信息，块间建 ST 表。这样修改是 $O(\sqrt n)$ 的，查询如果左右端点不同块是 $O(1)$ 的。然后我们递归进块内建这个结构，类似 sqrt tree 在查询的时候 $O(1)$ 定位到需要的层。

预处理复杂度是 $O(n \log \log n)$。

优点是好写，然后常数比（带修的）sqrt tree 要小。

测试题, 提交记录。

这是在洛谷静态 RMQ 上的提交记录。

如果还要更轻量级，可以考虑牺牲一点询问复杂度：

令 $m=\frac{\log(n)}{2}$，在 ST 表上仅维护前 $m$ 层，对于长度大于 $2^m$ 的询问我们直接暴力递归下去做，这样修改和询问都是单根号的，不过相比分块在大多数情况下没有显著优势。

这个东西唯一的用途可能是像 P10680 这样的带修倍增？

以上。