RMQ

[Ir1d]

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

OI Wiki 是一个编程竞赛知识整合站点，提供有趣又实用的编程竞赛知识以及其他有帮助的内容，帮助广大编程竞赛爱好者更快更深入地学习编程竞赛

[Seanq-master]

LCA也可以做一个专题吧，毕竟它有倍增、树剖、欧拉序+RMQ以及Tarjan等求法？

[GouBuliya]

我觉得可以

[Ir1d]

@Seanq-master 滋兹啊，欢迎 PR

[loceaner]

LCA也可以做一个专题吧，毕竟它有倍增、树剖、欧拉序+RMQ以及Tarjan等求法？
支持

[Henry-ZHR]

这里的最后一句是不是错了？不应该是“时间复杂度较大”吧？

[Alisia0182]

@loceaner
LCA也可以做一个专题吧，毕竟它有倍增、树剖、欧拉序+RMQ以及Tarjan等求法？
支持

在这里有的https://oi-wiki.org/graph/lca/

[w23c3c3]

线段树空间复杂度是O(n)的吧

[ChungZH]

Four Russian!

[TLEer-299922]

CSP2021前来考古

[l4v12o]

CSP2021前来考古

[woshixjk]

CSP2021前来考古

[chenyinjin2006]

建议加一个位运算向的经典结论专题

[Zaunese]

Stop learning useless algorithms, go and solve some problems, learn how to use binary search.

[hqztrue]

"Four Russian"那一节的算法失去了method of four russians的灵魂啊，2^S项才是核心的idea。感觉其实应该看成分块类算法

[Eletary]

可以开个 pr 改一下

[hhc0001]

脑洞时刻：既然 RMQ 可以被转化成 LCA，然后 LCA 又转化成 RMQ，不就无限循环了吗？

[wytsai7660]

最後一種方法（基于状压的线性 RMQ 算法）的具體單次查詢複雜度是多少？看不大明白

而且看代碼似乎實作難度頗高，這個方法在競賽中值得採用嗎？（目前我個人都是 動態->zkw線段樹，靜態->Sparse Table）

[robinyqc]

单次查询复杂度可以认为是 $O(1)$。瓶颈是那个叫做 __builtin_ctz 的内置函数，用来计算整数二进制下从低位算起有几个零（count trailing zero）。它由电脑硬件优化，所以效率非常高，与乘法效率差不多，比除法要快很多。

与这个函数相似的函数是 __builtin_clz (count leading zero)，计算整数二进制下从高位算起有几个零。这个函数在普通 ST 表有表现优异的运用。因为它可以计算对数向下取整：31 ^ __builtin_clz(x) 可以计算 $\left\lfloor \log_2(x)\right\rfloor$，这样你就可以不用打表计算 log 了。

关于实用性：
在竞赛中不太可能用上线性复杂度的 ST 表，如果某道题的正确解法要用上这个，出题人一定会被骂。
如果一定要用（也就是，普通 ST 表效率不够），这个做法不论是代码实现难度还是运行效率，应该都要比上文所提到的线性 RMQ (Four Russian) 好。因为通常这种情况，数组特别大，访问元素的常数大，故采用空间常数小的结构，并尽量少地访问数组，更占优。

不过上文提供的代码实现空间常数比较大。好一点的实现可以参考我在 Yosupo 的提交（其实也不是特别好但至少是 12n byte 的了）。

[stripepython]

Sqrt Tree也可以加进来吧