0x06 倍增

倍增，字面意思就是“成倍增长”。这是指我们在进行递推时，如果状态空间很大，通常的线性递推无法满足时间与空间复杂度的要求，那么我们可以通过成倍增长的方式，只递推状态空间中在2的整数次幂位置上的值作为代表。当需要其他位置上的值时，我们通过“任意整数可以表示成若干个2的次幂项的和”这一性质，使用之前求出的代表值拼成所需的值。所以使用倍增算法也要求我们递推的问题的状态空间关于2的次幂具有可划分性。

“倍增”与“二进制划分”两个思想互相结合，降低了求解很多问题的时间与空间复杂度。我们之前学习的快速幂其实就是“倍增”与“二进制划分”思想的一种体现。在本节中，我们研究序列上的倍增问题，包括求解RMQ（区间最值）问题的ST算法。关于求解最近公共祖先（LCA）等在树上的倍增应用，我们将在0x63节中进行探讨。

试想一个这样的问题：

给定一个长度为 $N$ 的数列 $A$ ，然后进行若干次询问，每次给定一个整数 $T$ ，求出最大的 $k$ ，满足 $\sum_{i=1}^{k} A[i] \leq T$ 。你的算法必须是在线的（必须即时回答每一个询问，不能等待收到所有询问后再统一处理），假设 $0 \leq T \leq \sum_{i=1}^{N} A[i]$ 。

最朴素的做法当然是从前向后枚举 $k$ ，每次询问花费的时间与答案的大小有关，最坏情况下为 $O(N)$ 。

如果我们能够先花费 $O(N)$ 的时间预处理 $A$ 数组的前缀和数组 $S$ ，就可以二分 $k$ 的位置，比较 $S[k]$ 与 $T$ 的大小来确定二分上下界的变化，每次询问花费的时间都是 $O(\log N)$ 。这个算法在平均情况下表现很好，但是它的缺点是如果每次询问给定的整数 $T$ 都非常小，造成答案 $k$ 也非常小，那么该算法可能还不如从前向后枚举更优。

我们可以设计这样一种倍增算法：

令 $p = 1$ ， $k = 0$ ， $sum = 0$ 。
比较 “ $A$ 数组中 $k$ 之后的 $p$ 个数的和”与 $T$ 的关系，也就是说，如果 $\text{sum} + S[k + p] - S[k] \leq T$ ，则令 $\text{sum} + = S[k + p] - S[k]$ ， $k += p, p *= 2$ ，即累加上这 $p$ 个数的和，然后把 $p$ 的跨度增长一倍。如果 $\text{sum} + S[k + p] - S[k] > T$ ，则令 $p/ = 2$ 。
重复上一步，直到 $p$ 的值变为0，此时 $k$ 就是答案。

这个算法始终在答案大小的范围内实施“倍增”与“二进制划分”思想，通过若干长度为2的次幂的区间拼成最后的 $k$ ，时间复杂度级别为答案的对数，能够应对 $T$ 的各种大小情况。

【例题】GeniusACM hihocoder#1384

给定一个整数 $M$ ，对于任意一个整数集合 $S$ ，定义“校验值”如下：

从集合 $S$ 中取出 $M$ 对数（即 $2 * M$ 个数，不能重复使用集合中的数，如果 $S$ 中的整数不够 $M$ 对，则取到不能取为止），使得“每对数的差的平方”之和最大，这个最大值就称为集合 $S$ 的“校验值”。

现在给定一个长度为 $N$ 的数列 $A$ 以及一个整数 $T$ 。我们要把 $A$ 分成若干段，使得每一段的“校验值”都不超过 $T$ 。求最少需要分成几段。

首先，对于一个集合 $S$ ，显然应该取 $S$ 中最大的 $M$ 个数和最小的 $M$ 个数，最大和最小构成一对、次大和次小构成一对……这样求出的“校验值”最大。而为了让数列 $A$ 分成的段数最少，每一段都应该在校验值不超过 $T$ 的前提下，尽量包含更多的数。所以我们从头开始对 $A$ 进行分段，让每一段尽量长，到达结尾时分成的段数就是答案。

于是，需要解决的问题为：当确定一个左端点 $L$ 之后，右端点 $R$ 在满足 $A[L] \sim A[R]$ 的校验值不超过 $T$ 的前提下，最大能取到多少。

求长度为 $N$ 的一段的校验值需要排序配对，时间复杂度为 $O(N \log N)$ 。当校验值上限 $T$ 比较小时，如果在整个 $L \sim N$ 的区间上二分右端点 $R$ ，二分的第一步就要检验 $(N - L)/2$ 这么长的一段，最终右端点 $R$ 却可能只扩展了一点儿，浪费了很多时间。与上一道题目一样，我们需要一个与右端点 $R$ 扩展的长度相适应的算法——倍增。

可以采用与上一题类似的倍增过程：

初始化 $p = 1$ ， $R = L$ 。
求出 $[L, R + p]$ 这一段区间的校验值，若校验值 $\leq T$ ，则 $R + = p$ ， $p * = 2$ ，否则 $p / = 2$ 。
重复上一步，直到 $p$ 的值变为0，此时 $R$ 即为所求。

上面这个过程至多循环 $O(\log N)$ 次，每次循环对长为 $O(R - L)$ 的一段进行排序，完成整个题目的求解累计扩展长度为 $N$ ，所以总体时间复杂度为 $O(N\log^2 N)$ 。实际上我们每次求校验值时可以不用快速排序，而是采用类似归并排序的方法，只对新增的长度部分排序，然后合并新旧两段，这样总体时间复杂度可以降低到 $O(N\log N)$ 。

ST算法

在RMQ问题（区间最值问题）中，著名的ST算法就是倍增的产物。给定一个长度为 $N$ 的数列 $A$ ，ST算法能在 $O(N\log N)$ 时间的预处理后，以0(1）的时间复杂度在线回答“数列 $A$ 中下标在 $l\sim r$ 之间的数的最大值是多少”这样的区间最值问题。

一个序列的子区间个数显然有 $O(N^2)$ 个，根据倍增思想，我们首先在这个规模为 $O(N^{2})$ 的状态空间里选择一些2的整数次幂的位置作为代表值。

设 $F[i,j]$ 表示数列A中下标在子区间 $[i,i + 2^j -1]$ 里的数的最大值，也就是从 $i$ 开始的 $2^{j}$ 个数的最大值。递推边界显然是 $F[i,0] = A[i]$ ，即数列 $A$ 在子区间 $[i,i]$ 里的最大值。

在递推时，我们把子区间的长度成倍增长，有公式 $F[i,j] = \max \left(F[i,j - 1], F[i + 2^j, j - 1]\right)$ ，即长度为 $2^j$ 的子区间的最大值是左右两半长度为 $2^{j-1}$ 的子区间的最大值中较大的一个。

void ST_prework() {  
    for (int i = 1; i <= n; i++) f[i][0] = a[i];  
    int t = log(n) / log(2) + 1;  
    for (int j = 1; j < t; j++)  
        for (int i = 1; i <= n - (1 << j) + 1; i++)  
            f[i][j] = max(f[i][j-1], f[i + (1 << (j-1))][j-1]);  
}

当询问任意区间 $[l, r]$ 的最值时，我们先计算出一个 $k$ ，满足 $2^k < r - l + 1 \leq 2^{k+1}$ ，也就是使 2 的 $k$ 次幂小于区间长度的前提下最大的 $k$ 。那么“从 $l$ 开始的 $2^k$ 个数”和“以 $r$ 结尾的 $2^k$ 个数”这两段一定覆盖了整个区间 $[l, r]$ ，这两段的最大值分别是 $F[l, k]$ 和 $F[r - 2^k + 1, k]$ ，二者中较大的那个就是整个区间 $[l, r]$ 的最值。因为求的是最大值，所以这两段只要覆盖区间 $[l, r]$ 即可，即使有重叠也没关系。

int ST_query(int l, int r) {
    int k = log(r - 1 + 1) / log(2);
    return max(f[l][k], f[r - (1 << k) + 1][k]);
}

简便起见，我们在代码中使用了cmath库的log函数。该函数效率较高，一般来说对程序性能影响不大。更严格地讲，为了保证复杂度为 $O(1)$ ，应该 $O(N)$ 预处理出 $1 \sim N$ 这 $N$ 种区间长度各自对应的 $k$ 值，在询问时直接使用。

0x06_倍增

0x06 倍 增

【例题】GeniusACM hihocoder#1384

ST算法

0x06 倍增