IceSandwich

积分表和差分表的使用

总结算法基础

算法
字数统计: 1.9k阅读时长: 7 min
2020/07/11 Share

先上一张图，一目了然

积分表

一个一维数组A，创建一个同长度的数组Integral，有：

$$Integral[n] = \sum_{i=0}^n A[n]$$

可以看到，积分表就是把前n个数加起来，这有什么好处呢？

积分表的几个特征：

  1. 积分表中两数之差，等于原数组相应索引的两数间(左开右闭)所有数之和

    比如：Integral[5]-Integral[2]=31-9=22，而A[3]+A[4]+A[5]=5+10+7=22，两者是相等的

    换句话说，利用积分表，求和运算变成了求两数之差。

  2. 若A中全为正数，积分表是单调递增的，积分表中最后一项是最大数，第一项是最小数

    很好理解吧，如果都是正数，那肯定越加越大，最后一项肯定最大，第一项肯定最小。

  3. 若A中全为正数，积分表是从小到大排序的

    跟第2个其实是一样的，但是这个排序性质很重要，我们可以利用这个特征做二分搜索，加快算法。

积分表例题 - 子序列 (POJ 3061)

题目：给定长度为n的数列正整数$a_0,a_1,\dots,a_n$以及整数$S$。求出总和不小于$S$的连续子序列的长度的最小值。如果解不存在，则输出0。

仔细分析题目，发现实质是要求恰好满足$a_s+a_{s+1}+\dots+a_{t-1} \ge S$时的s和t之差。

求和简单，问题是s和t怎么得到？

  1. 暴力法

    s从[0, 9]选取一个数，t从[0, 9]选取一个数，进行排列组合，复杂度$O(n^2)$，不可取

  2. 积分表

    求积分表sum，则原问题可转成恰好满足$sum[t-1]-sum[s-1] \ge S $时s和t之差。乍一看好像没什么变化，以为s和t还是需要排列组合，其实不然。我们把式子改成这样：$sum[t-1] \ge S + sum[s-1]$ 这样就变成了查找问题了，当定好s后，寻找t使得上面的式子成立即可。根据积分表性质3，这个查找可以用二分搜索得到，因此复杂度为$O(n\log{n})$

  3. 尺取法

    复杂度可降至$O(n)$，本文不讨论该方法。

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
/* POJ 3061 积分表法 AC代码 */
#include <iostream>
#include <algorithm>
using namespace std;

int sum[100000];

int solve(int N, int S) {
    int t;

    //Step 1. 计算积分表
    scanf("%d", &sum[0]);
    for (int i = 1; i < N; ++i) {
        scanf("%d", &t);
        sum[i] = sum[i-1] + t;
    }

    if (sum[N-1] < S) return 0; //解不存在

    //Step 2. 定好s，寻找t，保存最小长度
    int minLen = N;
    for (int s = 0; sum[s] + S <= sum[N-1]; ++s) {
        int t = lower_bound(sum + s, sum + N, sum[s] + S) - sum;
        minLen = min(minLen, t-s);
    }

    //Step 3. 完成
    return minLen;
}

int main() {
    int cases, N, S; scanf("%d", &cases);
    while (cases--) {
        scanf("%d%d", &N, &S);
        printf("%d\n", solve(N, S));
    }
    return 0;
}

差分表

一个一维数组A，创建一个同长度的数组Difference，有：

$$Difference[n]=A[n]-A[n-1]$$

值得注意的是，差分表是有符号方向的，+表示递增，-表示递减。

那差分表又有什么好处呢？

差分表的性质：

  1. 差分表中两数间所有数之和，等于原数组相对于的两数距离(含方向)

    比如：Difference[3]+Difference[4]+Difference[5]=2+5-3=4，A[5]-A[2]=7-3=4，两者是相等的

    也就是说，原数组两者之差，可以转为求和运算拉~

    额这。。。不是搞乱吗？怎么把求差变麻烦了？这个问题我们留到例子中说明。

  2. 差分表中从1加到最后的结果，等于原数组第一个和最后一个数的距离(含方向)

    其实就是性质1，只是把范围扩大到整个数组了。

差分表例题 - 最大子数组（算法导论第4章）

仔细看题，实质是求第i天和第j天的高度差最大，并且满足第i天比第j天低。

可能你会有以下想法：

  1. 求最低值和最高值，两者相减，高度差最大
  2. 求第二低的天，在那之后求最高值所在的位置，作为高度差最大
  3. 求第n低的天，在那之后求最高值所在的位置，求高度差，选择最大高度差的结果作为输出

以上1、2想法都是错的，原因：

  1. 没有考虑第i天比第j天低的情况

    算法求得最低点为绿点，最高点为橙点，但是绿点在橙点后，不符合题目要求。正确是紫点到橙点。

  2. 没有考虑第二低后面还会有个大跳跃

    第二低的点为绿点，之后最高点为橙点，但是中间的紫点更低，正确是紫点到橙点。

  3. 算法是正确的，这个就是暴力求解，遍历所有的可能。

可以看到，求高度差最大，其实就是求距离，而且要求低的在前，不就是差分表的方向性嘛。

  1. 暴力法

    就是上面的第3个思路，不讲了。

  2. 差分表+递归

    由性质1，求高度差，即求两数之间所有值的和。乍一看跟积分表的例题有点像，但是这里并没有告诉我们所求的和上限是多少，因此无法用二分搜索。因此这里结合分治思想使用差分表，差分表的结果是上图中价格变化表。

  3. 动态规划法或尺取法

    复杂度降至$O(n)$，不是本文讨论的内容。

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
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
#include <iostream>
#include <algorithm>
using namespace std;

const int N = 17;
int d[N] = {100,113,110,85,105,102,86,63,81,101,94,106,101,79,94,90,97};
int diff[N] = { 0 };

void findMaxCrossingSubArray(int s, int e, int mid, int &s_output, int &e_output, int &sum) {
    //Step 1. 中心往左边拓展，寻找最大和，sum([i, mid])
    int sum_left = 0, max_left = -1000;
    for (int i = mid; i >= s; --i) {
        sum_left += diff[i];
        if (max_left < sum_left) {
            max_left = sum_left;
            s_output = i;
        }
    }

    //Step 2. 中心往右边拓展，寻找最大和，sum([i, e])
    int sum_right = 0, max_right = -1000;
    for (int i = mid+1; i <= e; ++i) {
        sum_right += diff[i];
        if (max_right < sum_right) {
            max_right = sum_right;
            e_output = i;
        }
    }

    //Step 3. 求最大子数组的和
    sum = max_left + max_right;
}

void findMaxSubArray(int s, int e, int &s_output, int &e_output, int &sum) {
    #define RETURNN(ARGS, ARGE, ARGSUM) { s_output=ARGS; e_output=ARGE; sum=ARGSUM; }
    //Step 1. 递归结束条件
    if (s == e) {
        RETURNN(s, e, diff[s]);
        return;
    }
    int mid = (s+e)/2; //向下取值

    //Step 2. 对左边、中间、右边寻找最大子数组
    int s_left, e_left, sum_left;
    findMaxSubArray(s, mid, s_left, e_left, sum_left);
    int s_right, e_right, sum_right;
    findMaxSubArray(mid+1, e, s_right, e_right, sum_right);
    int s_mid, e_mid, sum_mid;
    findMaxCrossingSubArray(s, e, mid, s_mid, e_mid, sum_mid);

    //Step 3. 比较sum_left, sum_right, sum_mid，获取更大的子数组
    if (sum_left >= sum_right && sum_left >= sum_mid) {
        RETURNN(s_left, e_left, sum_left);
    } else if (sum_right >= sum_left && sum_right >= sum_mid) {
        RETURNN(s_right, e_right, sum_right);
    } else {
        RETURNN(s_mid, e_mid, sum_mid);
    }
}

int main() {
    //Step 1. 构造差分表
    diff[0] = 0;
    for (int i = 1; i < N; ++i) {
        diff[i] = d[i] - d[i-1];
    }

    //Step2. 求最大子数组
    int s, e, sum;
    findMaxSubArray(0, N-1, s, e, sum);

    printf("buy in %d, sold out %d, reach %d\n", s, e, sum);
    return 0;
}

输出结果是：buy in 8, sold out 11, reach 43

也就是，第7天交易结束后买入，从第8天开始计算收益，到第11天交易结束后卖出，此时收益最大，总收益43美元。

原文作者：IceSandwich

原文链接：https://icesandwich.github.io/2020/07/11/%E7%A7%AF%E5%88%86%E8%A1%A8%E5%92%8C%E5%B7%AE%E5%88%86%E8%A1%A8%E7%9A%84%E4%BD%BF%E7%94%A8/

发表日期：July 11th 2020, 12:00:00 am

更新日期：July 11th 2020, 3:49:38 pm

版权声明：本文采用知识共享署名-非商业性使用 4.0 国际许可协议进行许可

CATALOG
  1. 1. 积分表
    1. 1.1. 积分表例题 - 子序列 (POJ 3061)
  2. 2. 差分表
    1. 2.1. 差分表例题 - 最大子数组（算法导论第4章）
Total : 21
2021
2020
2019
c docker 算法 GTK 三维重建 KinectFusion 稠密重建 MSSQL html gtk opencv cuda BundleFusion 油猴脚本 js esp8266 arduino python torch Premiere FFmpeg 渗透
算法原理 docker GTK 三维重建 gtk BundleFusion 算法 脚本 硬件 研究 FFMPEG 渗透