算法竞赛进阶指南 基本算法 0x06 倍增

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

“倍增”与“二进制划分”两个思想互相结合，降低了很多时空复杂度；快速幂其实就是“倍增”与“二进制划分”思想的一种体现

研究序列上的倍增问题，包括求解RMQ（区间最值）问题的ST算法
求解最近公共祖先LCA等在树上的倍增应用，将在0x63节探讨

例题

题意 ：

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

思路 ：

• 朴素：从前往后枚举k，最坏情况为$O(N)$
• 若能够先花费$O(N)$时间预处理A的前缀和数组S，就可以二分k的位置，比较S[k]与T的大小，每次询问花费时间为$O(logN)$；这个算法在平均情况下表现很好；但缺点是如果每次询问给定的整数T都非常小，造成答案k也非常小，那么算法可能还不如从前往后枚举更优
• 我们可以设计这样一种 倍增算法：（通过若干长度为2的次幂的区间拼成最后的k，时间复杂度级别为答案的对数，能够应对T的各种大小情况）
  1、令 p = 1, k = 0, sum = 0;
  2、比较“A数组中k之后的p个数的和”与T的关系，也就是说，如果 sum + S[k + p] - S[k] <= T，则令 sum += S[k + p] - S[k], k += p, p *= 2，即累加这p个数的和，然后把p的跨度增长一倍；反之，如果大于，则令 p /= 2
  3、重复上一步，直到 p == 0，此时k就是答案
  4、注意我们这里还要加一个特判，因为p有可能小于k

int main() {
    cin >> n >> T;
    for (int i = 1; i <= n; ++ i) {
        cin >> a[i];
        s[i] = a[i] + s[i - 1];
    }
    int k = 0, p = 1, sum = 0;
    while (p) {
        if (sum + s[k + p] - s[k] >= T && s[k + p] > s[k]) {
            sum += s[k + p] - s[k];
            k += p;
            p *= 2;
        } else {
            p /= 2;
        }
    }
    cout << k;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

（-）AcWing 109. 天才ACM

ST算法

在RMQ区间最值问题中，著名的ST算法就是倍增的产物
给定一个长为N的数列A，ST算法能在$O(NlogN)$时间的预处理后，以$O(1)$时间复杂度在线回答“数列A中下标在l～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(F[i,j-1],F[i+2^{j-1},j-1])$，即长度为$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; ++ t)
        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]);
}
1
2
3
4
5
6
7

当询问任意区间[l, r]的最值时，我们先计算出一个k，满足$2^k\le r-l+1<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 - l + 1) / log(2);
    return max(f[l][k], f[r - (1 << k) + 1][k]);
}
1
2
3
4

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

P3865 【模板】ST 表

#include 
#include 
#define endl '\n'
#define _(a) cout << #a << ": " << (a) << "    "
using namespace std;
typedef long long ll;
typedef pair<int, int> PII;
const int N = 1e5 + 10, M = 20;

int n, m;
int a[N];
int f[N][M];

void ST_prework() {
    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]);
}
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]);
}

int main() {
    ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    cin >> n >> m;
    for (int i = 1; i <= n; ++ i) cin >> a[i];
    for (int i = 1; i <= n; ++ i) f[i][0] = a[i];
    ST_prework();
    while (m -- ) {
        int l, r;
        cin >> l >> r;
        cout << ST_query(l, r) << endl;
    }
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37

（-）LCA