[DS-5] 轻量级带修 ST 表！

Moeebius · 2024-07-31 22:55:06 · 科技·工程

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 这样的带修倍增？

以上。