倍增

算法
算法
发布日期:   2023-03-24
更新日期:   2024-12-20

倍增法，顾名思义就是翻倍。它能够使线性的处理转化为对数级的处理，大大地优化时间复杂度。

应用

RMQ 问题

参见：RMQ 专题

RMQ 是 Range Maximum/Minimum Query 的缩写，表示区间最大（最小）值。使用倍增思想解决 RMQ 问题的方法是 ST 表。

树上倍增求 LCA

参见：最近公共祖先

文章作者: Jarrycow
文章链接: http://jarrycow.top/posts/binary_lifting.html
版权声明: 本博客所有文章除特別声明外，均采用 CC BY 4.0 许可协议。转载请注明来源 Jarrycow !
算法
赏
评论
 上一篇
搜索 搜索
搜索，也就是对状态空间进行枚举，通过穷尽所有的可能来找到最优解，或者统计合法解的个数。
2023-04-14 算法
算法
下一篇 
二分查找 二分查找
二分查找，也称折半搜索、对数搜索，是用来在一个有序数组中查找某一元素的算法。
2023-03-24 算法
算法
  目录