《算法竞赛进阶指南》0x06 倍增

一只野生彩色铅笔

发布于 2022-10-31 10:58:51

6130

发布于 2022-10-31 10:58:51

文章被收录于专栏：彩铅的随笔博客

倍增基本概念

使用倍增算法，要求递推的问题的状态空间关于 2 的次幂具有可划分性

在进行递推时，如果状态空间很大，通常的线性递推无法满足时间和空间的要求

那么我们可以通过倍增的方式，只递推状态空间中在 2 的整数次幂位置上的值作为代表

当需要其他位置上的值时，我们通过 “任意整数可以表示成若干个 2 的次幂项的和” 这一性质，使用之前求出的代表值拼成所需的值

“倍增” 与 “二进制划分” 两个思想相互结合，降低了求解很多问题的空间与时间复杂度（例如：快速幂）

本节会讲解的内容：序列上的倍增问题，求解RMQ问题的ST表算法

后续树的章节还会介绍树上倍增求LCA

序列上的倍增问题

试想这样一个问题：

给定一个长度为

的序列

，然后进行若干次询问，每次给定一个整数

，求出最大的

，满足

\sum_{i=1}^kA_i \le T

。

算法要求强制在线，且

0 \le T \le \sum_{i=1}^n A_i

最朴素的做法是从前往后枚举

，每次询问花费的时间与答案的大小有关，最坏时间复杂度为

O(N)

通过简单观察发现，答案具有单调性，因此处理单次询问可以 “二分答案转化为判定”

又观察到每次判定，要用到前缀区间的元素和，因此想到再预处理出一个前缀和优化判定

这样做，处理单词询问的时间复杂度为：

O(\log N)

二分的解法在平均意义下表现很好，但是缺点在于如果每次询问给定的整数

非常小，导致答案

也很小，那么该算法可能还不如从前往后枚举更优

于是可以设计出这样一种倍增算法：

p = 1

k = 0

sum = 0

，其中

为 2 次幂跨度，

为当前前缀下标，

sum

为当前前缀和

比较 “

数组中

之后的

个数的和” 与 “

” 的关系

如果

sum + S_{k + p} - S_{k} \le T

，则令 sum += s[k + p] - s[k], k += p, p *= 2 即累加上这一段，并让

的跨度增长一倍

如果

sum + S_{k + p} - S_{k} \gt T

，则令 p /= 2

重复上一步，直到

的值变为

，此时

即为答案

int p = 1, k = 0, sum = 0;
while (p)
{
    if (sum + s[k + p] - s[k] <= T)
    {
        sum += s[k + p] - s[k];
        k += p;
        p *= 2;
    }
    else p /= 2;
}

这个算法始终在答案大小的范围内实施 “倍增” 与 “二进制划分” 思想，通过若干长度为

的次幂的区间拼成最后的

，时间复杂度为

O(\log k)

，能够应对

的各种大小情况。

而且序列上倍增还有一个规律，就是一开始

连续成倍增长，之后

连续折半递减。

ST算法

RMQ的经典应用就是ST表算法，很多人可能只知道RMQ，却不知道其就是倍增的一种产物

给定一个长度为

的序列

，ST算法能在

O(N\log N)

时间的预处理后，以

O(1)

的时间在线处理 “序列

的下标在

[l,r]

之间的数的最值是多少” 这样的区间最值询问

一个序列的子区间个数为

N^2

个，根据倍增的思想，首先在这

N^2

个状态空间里选择一些

的整数次幂的位置作为代表值

设

f[i, j]

表示序列

的子区间

[i, i + 2^j - 1]

里的最值

即从

开始(包括

) 的

2^j

个数的最大值

问题的边界显然是

F[i,0] = A_i

，递推式为：

F[i,j] = \max{F[i, j - 1], F[i + 2^{j-1}, j - 1]}

即区间

[i, i + 2^j - 1]

的最大值为区间

[i, i + 2^{i-1}-1]

与区间

[i + 2^{j-1}, i + 2^j - 1]

的最大值

再考虑一下

的范围：极限情况下是求区间

[1, n]

的最值，于是有

1 + 2^j - 1 \le n

化简易得：

2^j \le n \quad\Rightarrow\quad \log_{2}^{2^j} \le \log_{2}^{n} \quad\Rightarrow\quad j \le \log_2^n \quad\Rightarrow\quad j \le \lceil \log_2^n \rceil

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]

时，先计算出

，满足

2^k < r - l + 1 \le 2^{k+1}

，即小于区间长的最大

的

次幂

这样保证两个子区间：

[l, l + 2^k - 1]

和

[r - 2^k + 1, 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]);
}

log 函数为 cmath 库里的函数，因为其效率很高，因此我们近似看成

O(1)

无碍

习题

天才ACM

题目描述

给定一个整数

，对于任意一个整数集合

，定义“校验值”如下:

从集合

中取出

对数(即

2×M

个数，不能重复使用集合中的数，如果

中的整数不够

对，则取到不能取为止)，使得“每对数的差的平方”之和最大，这个最大值就称为集合

的“校验值”。

现在给定一个长度为

的数列

以及一个整数

我们要把

分成若干段，使得每一段的“校验值”都不超过

求最少需要分成几段

输入格式

第一行输入整数

，代表有

组测试数据

对于每组测试数据，第一行包含三个整数

第二行包含

个整数，表示数列

A_1, A_2, …, A_N

输出格式

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

数据范围

1≤K≤12

1≤N,M≤500000

0≤T≤10^{18}

0≤A_i≤2^{20}

输入样例：

输出样例：

2
1

解析

先考虑如何求一个集合的校验值？

结论：选出

个最大值和

个最小值，然后最大值配对最小值，次大值配对次小值 ......

证明：假设排序后的

个数为

a_1, a_2, \cdots, a_{2m}

按照上述策略配对，有：

|a_{2m}-a_1|^2 + |a_{2m-1}-a_2|^2 + \cdots + |a_{m+1}-a_{m}|^2

考虑交换配对

(a, b)

和

(c, d)

，其中

i < j

故有大小关系：

a < c < d < b

，校验值为：

(d-c)^2 + (b - a)^2

交换配对后，有两种情况，第一种情况为：

(a, c)

和

(d, b)

其校验值为：

(c-a)^2 + (b - d)^2

，两个等式作差易得：

[ \frac{1}{2}(v_1 - v_2) = ac + bd - cd - ab = b(d-a) - c(d-a) = (b-c)(d-a) \ge 0 ]

交换之后，显然方案不会变差，第二种情况为：

(a, d)

和

(c, b)

其校验值为：

(d-a)^2 + (b-c)^2

，两个等式作差易得：

[ \frac{1}{2}(v_1-v_3) = ad+bc-cd-ab = -d(c-a) + b(c-a) = (c-a)(b-d) \ge 0 ]

交换之后，显然方案不会变差

\mathbf{QED}

考虑如何分段？

由于题设要求是分成的段数尽可能少，因此每段要求尽可能长，这就与“序列前缀区间和询问”一样了

不过那一题是求前缀区间和不少于

，这一题是前缀校验值不少于

这题就会体现出 “倍增” 和 “二分” 的区别了

由于每次要判定当前的答案是否满足条件，因此每次判定，都要对答案区间进行排序，然后配对

“倍增” 和 “二分” 找答案的时间复杂度基本一致，差的只是常数，但问题主要出现在答案判定上

如果用二分，每一次二分的中点就是

mid = \frac{l + n}{2}

，这个

mid

与

是一个数量级的

因此如果答案的每个段很小，那么每次排序复杂度为

O(n\log n)

，总复杂度是

O(n^2\log n)

如果用 “倍增” 寻找答案，他会从小区间往大区间扩展，效率高于二分，这里可以给出数学证明：

假设倍增到答案过程中判定的区间长度分别为：

l_1, l_2, \cdots, l_k

，先考虑单次分段倍增的复杂度：

[ O\Big(\sum _{i=1}^k l_i\log l_i) \le O(\log n \times \sum_{i=1}^k l_i\Big) \le O(\log n \times \sum_{i=1}^k l_k) \le O(\log n \times \log n l_k) = O(l_k \log^2 n) ]

将所有的段加起来，总的时间复杂度为：

O(n \log^2 n)

远远优于二分做法

倍增过程如下：

初始化

p = 1

R = L

求出

[L, R + p]

这一段区间的校验值：

若校验值

\le T

，则 R += p, p *= 2

若校验值

\gt T

，则 p /= 2

重复上一步，直到

变为

为止，此时

即为所求

bool check(int l, int r)
{
    int k = 0;
    for (int i = l; i < r; i ++ ) b[k ++ ] = a[i];
    sort(b, b + k);
    LL sum = 0;
    for (int i = 0; i < m && i < k; i ++ , k -- )
        sum += (LL) (b[i] - b[k - 1]) * (b[i] - b[k - 1]);
    return sum <= T;
}
void solve()
{
    scanf("%d%d%lld", &n, &m, &T);
    for (int i = 0; i < n; i ++ ) scanf("%d", &a[i]);
    int l = 0, cnt = 0;
    while (l < n)
    {
        int p = 1, r = l;
        while (p)
        {
            if (r + p <= n && check(l, r + p))
            {
                r += p;
                p *= 2;
            }
            else p /= 2;
        }
        cnt ++ ;
        l = r;
    }
    printf("%d\n", cnt);
}

二路归并优化

不难发现，在倍增的过程中，排序的片段中前缀数组已经有序（因为上一轮倍增好后排好了）

即

[l, r)

已经有序，现在倍增需要检验的区间为

[l, r + p)

如上面的做法，采用直接对

[l, r + p)

区间排序的策略，最终的时间复杂度为

O(n\log^2n)

既然前缀区间已有序，不妨只排

[r, r + p)

，再将两个区间做一次 二路归并，单次分段的时间复杂度如下：

[ O\Big(\sum_{i=1}^k [(l_i - l_{i-1}) \log (l_i - l_{i-1}) + l_i]\Big) = O\Big(\sum_{i=1}^k [(l_i - l_{i-1}) \log (l_i - l_{i-1})]\Big) = O\Big(l_k \log l_k\Big) ]

这样总的时间复杂度为：

O(n\log n)

，是本题的最优解

bool check(int l, int mid, int r)
{
    for (int i = mid; i < r; i ++ ) b[i] = a[i];
    sort(b + mid, b + r);
    int i = l, j = mid, k = 0;
    while (i < mid && j < r)
    {
        if (b[i] < b[j]) t[k ++ ] = b[i ++ ];
        else t[k ++ ] = b[j ++ ];
    }
    while (i < mid) t[k ++ ] = b[i ++ ];
    while (j < r) t[k ++ ] = b[j ++ ];
    
    LL sum = 0;
    for (int i = 0; i < m && i < k; i ++ , k -- )
        sum += (LL) (t[i] - t[k - 1]) * (t[i] - t[k - 1]);
    return sum <= T;
}
void solve()
{
    scanf("%d%d%lld", &n, &m, &T);
    for (int i = 0; i < n; i ++ ) scanf("%d", &a[i]);
    int l = 0, cnt = 0;
    while (l < n)
    {
        int p = 1, r = l;
        while (p)
        {
            if (r + p <= n && check(l, r, r + p))
            {
                r += p;
                p *= 2;
                for (int i = l; i < r; i ++ )
                    b[i] = t[i - l];
            }
            else p /= 2;
        }
        cnt ++ ;
        l = r;
    }
    printf("%d\n", cnt);
}

本文参与腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。

原始发表：2022-01-28，如有侵权请联系 cloudcommunity@tencent.com 删除

编程算法

本文分享自作者个人站点/博客前往查看

如有侵权，请联系 cloudcommunity@tencent.com 删除。

本文参与腾讯云自媒体同步曝光计划，欢迎热爱写作的你一起参与！

编程算法

登录后参与评论

0 条评论

热度