大四的萌新辣！

倍增

Posted on Edited on In Valine:

今天来介绍一种算法竞赛中对于问题优化的新技巧 - - 倍增

倍增主要是一种技巧可以大大优化时间复杂度的算法，主要常用来解决$RMQ$(区间最值)问题以及关于$LCA$(最近公共祖先)在树上倍增的技巧,以及对倍增的扩展 — ST表

倍增初探

倍增，字面意思 成倍增长，主要是对于一些递推问题，如果其状态空间很大，无法满足复杂度要求，所以我们可以通过成倍增长来只递推状态空间中在$2$的整数次幂上的值作为代表，对于其他值，我们可以通过性质任意整数可以表示成若干个2的次幂项的和 来表示出整数。

1
2
3
1 2 4 8 ... 2^k // 2的幂次项

1 ~ 2 ^ (k + 1) - 1 // 可以表示的整数的范围

因此对于倍增算法，我们对其问题的状态空间关于$2$的·幂次要有可划分性。

问题引入

给你一个长度为$N$的序列$A$,满足序列$A$中的所有元素都是正整数,然后进行$M$次询问,每次给定一个整数$T$,求出最大的$k$,满足$\sum_{i = 1}^k {A[i]} <= T$.

要求：算法必须是在线的 也就是说 必须收到一个询问就即时回答,不能收到$M$个询问后统一回答.

假设: $0 <= T <= \sum_{i = 1}^N {A[i]}$

解决方案

  1. 朴素做法：

开一个变量$sum$，然后每次询问的时候从前往后扫一遍并且$sum$累加 $if$判断一下

该算法与$T$有关 $T$越大,时间复杂度越高 最坏情况下 时间复杂度可以达到$O(n * m)$

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
38
39
40
41
/**
* Copyright(c)
* Author : tiketiskte
**/
#include <bits/stdc++.h>
#define IOS {ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);}
#define ll long long
#define PLL pair<ll, ll>
#define SZ(X) (int)X.size()
#define INF 0x3f3f3f3f

using namespace std;

const int maxn = 100 + 5;
int n,m;
int a[maxn];
int ans;
ll T, sum;
int main(void)
{
    IOS
    cin >> n >> m;
    for(int i = 1; i <= n; i++) {
        cin >> a[i];
    }
    while(m--) {
        sum = 0;
        cin >> T;
        for(int i = 1; i <= n; i++) {
            if(sum + a[i] >= T) {
                ans = i - 1;
                break;
            } else {
                sum += a[i];
            }
        }
        cout << ans << endl;
    }
    system("pause");
    return 0;
}
  1. 二分答案

我们可以发现，既然序列$A$中的元素均为正整数，则对于其求前缀和可以求得一个单调递增的序列。即$\sum_{i = 1}^k {A[i]}$单调递增。

因此满足答案的分段且单调的性质，故可以二分答案求解。

二分答案找到中值点$mid$，计算$\sum_{i = 1}^{mid} {A[i]}$ 和$T$的大小关系

更新二分区间范围

我们可以通过前缀和在$O(n)$的复杂度内求出来$sum[i]$，我们选择时，最少选$0$次,最多选$n$次,所以一共二分$O(log n)$次，与$T$无关。

缺陷在于：当$T$很小时，二分次数保持不变，在一定程度上，性能劣与方法一。例如$N$取$1000000$时，$logn$约为$20$，若$T$为$1$，则显然方法一更优。

总的时间复杂度：$O(logn * m)$ 常数较大qwq

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
38
39
40
41
42
43
44
45
46
47
48
49
50
/**
* Copyright(c)
* Author : tiketiskte
**/
#include <bits/stdc++.h>
#define IOS {ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);}
#define ll long long
#define PLL pair<ll, ll>
#define SZ(X) (int)X.size()
#define INF 0x3f3f3f3f

using namespace std;

const int maxn = 100 + 5;
int n,m;
int a[maxn], b[maxn];
int ans;
ll T, sum;
int check(int mid) {
    return b[mid];
}
int main(void)
{
    IOS
    cin >> n >> m;
    for(int i = 1; i <= n; i++) {
        cin >> a[i];
    }
    b[1] = a[1]; 
    for(int i = 2; i <= n; i++) {
        b[i] = b[i - 1] + a[i];
    }
    while(m--) {
        sum = 0;
        cin >> T;
        int l = 1, r = n;
        while(l < r) {
            int mid = (l + r) >> 1;
            if(check(mid) < T) {
                l = mid + 1;
            } else {
                r = mid;
            }
            ans = mid;
        }
        cout << ans << endl;
    }
    system("pause");
    return 0;
}
  1. 倍增优化

我们可以考虑倍增, 用一个变量$len$记录每一次的步长。然后我们判断当某一步不满足条件的时候，我们取上一次步长和这一次步长的中点值(二分思想),最终找到合适的点满足条件。

对于该算法，相当于稳定版本的“二分法”,我们查找时，按照$2^k$进行遍历，如果不满足，则折半查找，对于$sum$可能到达$2^k$时,大于$T$，则其总和为$2^{k + 1} - 1$,折半后，最坏情况下达到$2^{k - 1}$,其总和为$2^k - 1$

即最坏情况下，会遍历$2k$次，$k$与$n$和$T$都有关

  • $2^k <= n$ $\quad$ -> $\quad$ $k <= lg n$
  • $T$增大，则遍历次数$k$随之增大

因此，对与倍增算法，其最坏情况下达到$O(log n)$的时间复杂度，但随着$T$正比例改变，显然优于二分算法。

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
38
39
40
41
42
43
44
45
46
47
48
49
/**
* Copyright(c)
* Author : tiketiskte
**/
#include <bits/stdc++.h>
#define IOS {ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);}
#define ll long long
#define PLL pair<ll, ll>
#define SZ(X) (int)X.size()
#define INF 0x3f3f3f3f

using namespace std;

const int maxn = 100 + 5;
int n,m;
int a[maxn], b[maxn];
int ans;
ll T, sum;
int check(int x) {
    return b[x];
}
int main(void)
{
    IOS
    cin >> n >> m;
    for(int i = 1; i <= n; i++) {
        cin >> a[i];
    }
    b[1] = a[1];
    for(int i = 2; i <= n; i++) {
        b[i] = b[i - 1] + a[i];
    }
    while(m--) {
        cin >> T;
        int len = 1, k = 0;
        while(len) {
            if(k + len <= n && b[k + len] <= T) {
                k += len; // k = k + len
                len <<= 1;
            } else {
                len >>= 1;
            }
        }
        ans = k;
        cout << ans << endl;
    }
    system("pause");
    return 0;
}

倍增扩展

占坑待补qwq~

  1. ST表

  2. LCA在线算法 (求最近公共祖先)