ST 表

[Ir1d]

https://oi-wiki.org/ds/sparse-table/

[morris821028]

補充：稀疏表+分塊思維+塊內笛卡爾樹，詢問時間複雜度 O(1)，空間複雜度 O(n)，建表複雜度 O(n)

[ouuan]

補充：稀疏表+分塊思維+塊內笛卡爾樹，詢問時間複雜度 O(1)，空間複雜度 O(n)，建表複雜度 O(n)

https://oi-wiki.org/topic/rmq/#four-russian

[morris821028]

@ouuan
https://oi-wiki.org/topic/rmq/#four-russian

https://en.wikipedia.org/wiki/Range_minimum_query#Solution_using_constant_time_and_linear_space

複雜度分析不對

[ouuan]

@ouuan
https://oi-wiki.org/topic/rmq/#four-russian

https://en.wikipedia.org/wiki/Range_minimum_query#Solution_using_constant_time_and_linear_space

複雜度分析不對

https://oi-wiki.org/topic/rmq/#rmq

[morris821028]

@ouuan
https://oi-wiki.org/topic/rmq/#rmq

先問個四個俄羅斯人算法好了，維基百科上寫的是針對二維布林矩陣為主的計算，RMQ 只能算是用上分塊想法，跟四個俄羅斯人的核心是不太相同的。

隨後說用笛卡爾樹優化前一個四個俄羅斯人算法就會稍微奇怪，我們是透過塊建立的不同笛卡爾樹的樹形去取代原先的建表方法，由於二元樹種類為卡塔蘭數，乘上所有塊內的區間對數，最後為線性空間。

[lucheng2]

ST表，对应的英文是Sparse Table，稀疏表。

[lsy1109]

什么是手动模拟啊

[hatrd]

有个小细节，C++模板里，query传入l==r时会运行时错误。

[wholvecoding]

拆分区间的那一步应该是2^(s-1) 吧

[Minecraftwhr]

不是，还论风格的吗

[Po00iu6]

上来就是一个class，对CSP级别的OIer很不友好啊，能写成CSP级别的OIer能看懂的不？

[typed-sigterm]

建议学学语言，而不是只学算法

[imarkzzz]

x opt x = x，就是幂等性

[CLimber-Rong]

花了很长时间才搞懂状态转移方程是怎么推导出来的，发现评论区没有详细解释。

具体是哪里难懂呢？ $f(i+2^{j-1}, j-1)$ 比较难懂。

本评论提供简单的推导过程。

已知： $f(i,j)$ 代表 $[i, i+2^j-1]$ 的最大值
所以：

$$ f(i,j) = [i, i+2^j-1]的最大值 = max( [i, i+2^{(j-1)}-1]的最大值, [i+2^{(j-1)}, i+2^j-1]的最大值) $$

留意到：

$$ i+2^j-1 = i+2 \times 2^{j-1}-1 = i+2^{j-1}+2^{j-1}-1 （即为①） $$

（即 $2^j$ 能拆成两个 $2^{j-1}$ ）

由①得：

$$ i+2^{j-1}+2^{j-1}-1 = (i+2^{j-1})+(2^{j-1}-1) = f(i+2^{j-1}, j-1) $$

综上，能得出 $f(i+2^{j-1}, j-1)=[i+2^{(j-1)}, i+2^j-1]的最大值$
（应该不需要解释为什么 $f(i, j-1)=[i,i+2^{j-1}-1]的最大值$ 了吧）


综上，方程 $f(i,j) = max(f(i,j-1), f(i+2^{j-1}, j-1))$ 就能推导出来了。
（当然，把 $f(i+2^{j-1}, j-1)$ 反推也是一种方法，但是有点不知其所以然的感觉）

[lkjlkjlkj2012]

Sparse Table本身是不是就带了“表”字，翻译时又加上了一个“表”……

[weilycoder]

2025 年了，不要再使用 logn 数组预处理 $\left\lfloor log_2 x\right\rfloor$ 了；相信 CPU，读取内存的速度会慢于调用内置函数的速度。

size_t fast_log2(size_t x) { return 63 - __builtin_clzll(x); }

[AC-13-13]

LCA (最近公共祖先) 其实也是 「可重复贡献问题」吧，但其实……额……没什么用