倍增

倍增简介

• 倍增（BinaryLifting）是一种常用的解决问题的思想，之前我们已经用倍增解决过树上最近公共祖先问题。

• 假设现在我们要查询×步以后的情况，倍增的核心思想是：

• 1. 我们需要快速处理出所有 2k(k≥0) 步以后的情况;
  • 初始我们知道 1(2^0) 步以后的情况
  • 假如我们已经求出了 2^y(y≥0）步以后的情况，我们要以此为基础求出 2^(y + 1) 步以后的情况；
• 2. 把×拆成 log(x) 份 2 的幂次方的和，然后我们依次往后走这么多了

• 倍增的时间复杂度取决于这两步我们做得有多快！