跳转至

倍增

倍增法,通过字面意思来看就是翻倍。这个方法在很多算法中均有应用,其中最常用的就是 RMQ 问题和求 LCA 了。

RMQ 问题

RMQ 是英文 Range Maximum/Minimum Query 的缩写,表示区间最大(最小)值。

解决 RMQ 问题的主要方法有两种,分别是 ST 表和线段树,具体请参见 ST 表 页面和 线段树 页面。

树上倍增求 LCA

具体请参见 最近公共祖先 页面。


评论