算法基础-倍增

参考资料：倍增 - OI Wiki

倍增

定义

倍增法（binary lifting），即“成倍增长”的含义。我们在进行递推时，如果状态空间很大，那么通常的线性递推无法满足空间和时间复杂度的要求。那么，我们可以通过成倍增长的方式，只递推状态空间中在 \(k\) 的整数次幂位置上的值作为代表。当需要其他位置上的值时，我们通过k的一元多项式之和得到。所以使用倍增算法也要求我们递推的问题的状态空间关于 \(k\) 的次幂具有可划分性。通常情况下 \(k\) 取 \(2\) （这样每项的系数要么为 \(1\) ，要么为 \(0\) ）

应用

RMQ问题

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

树上倍增求LCA

求最近公共祖先的倍增解决方式