基于分块优化的ST表

· · 算法·理论

注意，为了偷懒，部分系数被省略。

注意到，普通 ST 表查询区间最值需要执行 (M+N\log N) 次，理论空间开销大约为 8(N+N\log N) 字节（用 64 位有符号整形存的话），在 N 和 M 极大时就算时间能过，空间也过不了，于是就可以想到用分块优化。

我们设我们的块长为 B，方案为对序列进行分块，维护出每块的最值，再用 ST 表维护出每个块的最值，查询时如果在一个块内，则暴力扫描最值，否则把他拆成左端点到其所在块最右端的最值，右端点到其所在块左端点的最值，中间完整的块部分的最值。其中完整的块的最值用 ST 表查，不完整的直接暴力查。

那么最坏情况下的执行次数为 N+\frac{N}{B}\log \frac{N}{B}+MB，空间为 8(N+\frac{N}{B}\log \frac{N}{B}) 字节。

因此我们就可以对应的求出最优的 B，画出函数图像可以发现，随着 N,M 的增加，B 的最优值在缓慢向右移动，当 N=M=10^5 或 10^6 时，B=4 最合适，而当到了 10^7 甚至 10^8 时，B=5 最合适（当然，当 N=M=10^8 显然无论如何会超时）。但是如果一道题卡空间的话，因为空间的函数是减函数，所以将 B 适量增加即可。

尽管数学推倒结果显示 B 最优是 4 或 5，但在处理 P3793 时发现 B=16 才是最优的，根据 AI 这是因为现代主流 CPU 的一个 Cache Line 大小通常是 64 字节。一个 int 占用 4 字节。4 \times 16 = 64 字节。这意味着当 B=16 时，每一个块在内存中正好占据一个完整的 Cache Line。于是我有试了一下 B=15 和 B=17，发现确实没有 B=16 快，表明这应该就是原因（4 空间超了，5 超时，15,17,32 没有 16 优秀，64 超时）。

由此我们也可以看出，分块不一定是取 N^{\frac{1}{2}} 最合适，要根据实际情况求出合理的块长。

当然其实还可以进一步优化，使得在同一块内也可以直接查找，且优化了空间，可以参考 https://oi-wiki.org/topic/rmq/#%E5%9F%BA%E4%BA%8E%E7%8A%B6%E5%8E%8B%E7%9A%84%E7%BA%BF%E6%80%A7-rmq-%E7%AE%97%E6%B3%95 。

总结一下，就是此法一般用于减小空间复杂度，因为此法比普通 ST 表相比代码量更大，在空间够的情况下直接写普通 ST 表即可。