倍增 | 基本算法

参考《算法竞赛进阶指南》、AcWing题库

倍增

倍增简介

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

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

倍增例题：

给定一个长度为 $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$ 也非常小, 那么该算法可能还不如从前向后枚举更优。

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

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

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

---

109. 天才ACM

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

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

现在给定一个长度为 $N$ 的数列 $A$ 以及一个整数 $T$。

我们要把 $A$ 分成若干段，使得每一段的“校验值”都不超过 $T$。

求最少需要分成几段。

输入格式

第一行输入整数 $K$，代表有 $K$ 组测试数据。

对于每组测试数据，第一行包含三个整数 $N,M,T$ 。

第二行包含 $N$ 个整数，表示数列$A_1,A_2…A_N$。

输出格式

对于每组测试数据，输出其答案，每个答案占一行。

数据范围

$1 \le K \le 12$,
$1 \le N,M \le 500000$,
$0 \le T \le 10^{18}$,
$0 \le A_i \le 2^{20}$

输入样例：

2
5 1 49
8 2 1 7 9
5 1 64
8 2 1 7 9 

输出样例：

2
1 

算法分析

首先, 对于一个集合 $S$, 显然应该取 $S$ 中最大的 $M$ 个数和最小的 $M$ 个数, 最大和最小构成一对、次大和次小构成一对 $\cdots$ 这样求出的 “校验值” 最大。而为了让数列 $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$ 扩展的长度相适应的算法一一倍增。 可以采用与上一题类似的倍增过程:

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

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

#include <cstdio>
#include <iostream>
#include <algorithm>
#define ll long long
using namespace std;
const int N = 500006;
int n, m, w;
ll k, a[N], b[N], c[N];

void gb(int l, int mid, int r) {
	int i = l, j = mid + 1;
	for (int k = l; k <= r; k++)
		if (j > r || (i <= mid && b[i] <= b[j])) c[k] = b[i++];
		else c[k] = b[j++];
}

ll f(int l, int r) {
	if (r > n) r = n;
	int t = min(m, (r - l + 1) >> 1);
	for (int i = w + 1; i <= r; i++) b[i] = a[i];
	sort(b + w + 1, b + r + 1);
	gb(l, w, r);
	ll ans = 0;
	for (int i = 0; i < t; i++)
		ans += (c[r-i] - c[l+i]) * (c[r-i] - c[l+i]);
	return ans;
}

void Genius_ACM() {
	cin >> n >> m;
	cin >> k;
	for (int i = 1; i <= n; i++) scanf("%lld", &a[i]);
	int ans = 0, l = 1, r = 1;
	w = 1;
	b[1] = a[1];
	while (l <= n) {
		int p = 1;
		while (p) {
			ll num = f(l, r + p);
			if (num <= k) {
				w = r = min(r + p, n);
				for (int i = l; i <= r; i++) b[i] = c[i];
				if (r == n) break;
				p <<= 1;
			} else p >>= 1;
		}
		ans++;
		l = r + 1;
	}
	cout << ans << endl;
}

int main() {
	int t;
	cin >> t;
	while (t--) Genius_ACM();
	return 0;
}

Solution

---

ST 算法

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

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

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

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

// 区间最值问题的ST算法
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 \leq2^{k+1}$, 也就是使 2 的 $k$ 次幂小于区间长度的前提下最大的 $k$ 。那么 “从 $l$ 开始的 $2^{k}$ 个数” 和 “以 $r$ 结尾的 $2^{k}$ 个数” 这两段一定覆盖了整个区间 $[l, r]$, 这两段的最大值分别是 $F[l, k]$ 和 $F\left[r-2^{k}+1, k\right]$, 二者中较大的那个就是整个区间 $[l, r]$ 的最值。因为求的是最大值, 所以这两段只要覆盖区间 $[l, r]$ 即可, 即使有重叠也没关系。

int ST_query(int l, int r) {
	int k = log(r - l + 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$ 值, 在询问时直接使用。