倍增

♠ use C++11

倍增法和二分法可以说是“相反”的算法，效率都很高。二分法是每次缩小一半，从而以 \(\mathcal{O}(\log n)\) 的速度极快地缩小定位到解；倍增法是每次扩大一倍,也是 \(\mathcal{O}(\log n)\) 速度。

倍增就是“成倍增长”，如何实现倍增，是每步乘以 2 吗？有时确实可以,如后缀数组，每次扩展字符长度，就简单地乘以 2。不过，在大多数题目中有更好的实现方法，即利用二进制本身的倍增特性。

一般地，倍增是通过数组来完成的。可以设 \(f_{i,j}\)，代表 \(i\) 结点向上跳 \(2^j\) 步所能到达的父节点。首先是预处理：\(f_{i,0}=i\)，然后我们知道：\(2^k=2^{k-1}+{(k-1)}\)，因此可以得出 \(f_{i,j}=f_{(f_{i-1,j-1}),j-1}\)。

倍增法的局限性是数据要是静态不变的，而不是动态变化的。如果数据发生了变化，那么所有跳板需要重新计算，倍增就失去了意义。

例题。