倍增思想

前置知识

对二进制有一定的理解

引言

倍增思想的本质是：

每次根据已经得到的信息，将考虑的范围扩大一倍，从而加速操作。

主要有两个方面的应用：

一、在变化规则相同的情况下，加速状态转移

二、加速区间操作

在变化规则相同的情况下加速状态转移

加速区间操作

此处，查看 ST表、LCA 相关内容。

总结

倍增思想

一、每次的变化规则必须相同

二、变化规则必须满足结合律

倍增思想所作用的对象实际上是变化规则，而并非具体的状态！

倍增思想的作用是算出一个状态到另一个状态的变化量。也就是说，倍增思想计算出的量与具体的状态是无关的，而仅与状态之间的关系有关。

// 我们从这个角度，对快速幂的模板代码，进行新的理解
int qmi(int a, int k, int p)
{
    int res = 1; 
    while (k)
    {
        if (k & 1) res = 1ll * res * a % p; // 对 res 这个状态，施行变化规则
        k >>= 1;
        a = 1ll * a * a % p; // 变化规则 * 变化规则
    }
    return res;
}

在实际情况中，

\(a\) 可能是一个实数，也可能是一个矩阵，也可能是一个抽象的状态。

变化规则也可以是其他操作（如矩阵乘法、动态规划的状态转移等）

只要符合：

一、每次的变化规则必须相同

二、变化规则必须满足结合律

就可以应用倍增思想，并采用类似的方法加速计算。

参考

• 国家集训队2005论文集《浅析倍增思想在信息学竞赛中的应用》安徽省芜湖市第一中学 朱晨光