Aczy156

Algorithm13 前缀和与差分

[TOC]

前缀和与差分

压缩时间复杂度：只要降一个等级的复杂度即可达到题解的情况

经典情景：

  • 求和
  • 计算个数

【下边的时间复杂度分析只针对选取左上和右下的端点】

O(n^2) => O(n) ：一维上选取和最大的子区间

O(n^4) => O(n^3) ：二维上选取区域和最大的子区间

O(n^5) => O(n^4) ：定位了子区间之后，再加上一层遍历的点

一维的 最大子区间和

https://www.luogu.com.cn/problem/P1115

题目大意：一维数组，求最大子区间的和

（一）、前缀和思想：维护一个sum来描述当前索引位置之前的是否要存留。大于零就存储，小于零就归零。

#include <iostream>
using namespace std;
int n, prefix, tem, ans=1<<31;

int main() {
    scanf("%d%d", &n, &prefix);
    while (--n) {
        scanf("%d", &tem);
        prefix += tem;
        ans = max(ans, prefix);
        if (prefix < 0) prefix = 0;
    }
    printf("%d\n", ans);
    return 0;
}

（二）、dp思想

1、dp[i]表示当前位置之前的、包含自己的最大的子段，也就是说最大的要不就是单独的自己、要不就是自己加上前面的任意长度。dp[i] = max(dp[i-1]+now, now);

2、在最后要遍历一边所有的dp，也就是所有的位置上最长的，而不只是最后的那个dp[n]，是要筛选出dp[1]~dp[n]中最大的

#include <iostream>
using namespace std;
int ans = -999999, tmp, i, n, dp[200100] = {0};

int main() {
    scanf("%d", &n);
    for (i = 1; i <= n; ++i) {
        scanf("%d", &tmp);
        dp[i] = max(dp[i - 1] + tmp, tmp);
        ans = max(ans, dp[i]);
    }
    printf("%d\n", ans);
    return 0;
}

二维的 最大子区域和

https://www.luogu.com.cn/problem/P1719

题目：二维数组，求最大子区域（矩形）的和

方法1：利用前缀和，在单个方向压缩时间出一个O(n)，然后总的压缩成O(n^3)

方法2：先O(n^2)初始化，然后预处理成所有点到左上角的距离，然后再依次遍历两个维度的起点和终点，利用前缀和直接得到和

1、分两步和两个方向，每一步各自对应一个方向：

a) 第一步在行或者列二选一的方向上进行计算前缀和=>来进行压缩(本次压缩选择的是列上进行压缩，然后)a[i][j] += a[i-1][j]，也就是将每一列的和都压缩起来。

b) 第二部在上一步选的剩余的方向上进行提取：思想类似于上面的一维的遍历，从上往下前i行，然后用k做隔断，然后横向上在j做索引看每个i，j上的点在以k为隔断的最大值。

最终少了一个索引的原因 ：因为两个方向遍历，每个方向上都有一对起始索引，两个方向（横纵），索引复杂度理应O(n^4)，但是由于数据预处理利用前缀和进行压缩，再利用dp来提取max，所以复杂度降到O(n^3)。原理类似于上面一维的，一个方向一对起始索引O(n^2)，降到了O(n)

方法1：用前缀和，单方向压缩，然后总的压缩成O(n^3)

#include <iostream>
using namespace std;
#define maxn 125
int n, prefix[maxn][maxn], ans=1<<31;

int main() {
    scanf("%d", &n);
    for (int i = 1; i <= n; ++i) {
        for (int j = 1; j <= n; ++j) {
            scanf("%d", &prefix[i][j]);
            prefix[i][j] += prefix[i-1][j];
        }
    }
    for (int i = 1; i <= n; ++i) {
        for (int k = 1; k <= i; ++k) {
            int t[maxn]={0}, dp[maxn]={0};
            for (int j = 1; j <= n; ++j) {
                t[j] = prefix[i][j]-prefix[i-k][j];
                dp[j] = max(dp[j-1]+t[j], t[j]);
                ans = max(ans, dp[j]);
            }
        }
    }
    printf("%d\n", ans);
    return 0;
}

方法2：初始化，表示当前点到左上角的区域的前缀和的值，然后直接遍历两个边上的起点和终点。

#include <iostream>
using namespace std;
#define maxn 125
int n, prefix[maxn][maxn], ans=0;

int main() {
    scanf("%d", &n);
    for (int i = 1; i <= n; ++i)
        for (int j = 1; j <= n; ++j){
            scanf("%d", &prefix[i][j]);
            prefix[i][j] += prefix[i-1][j]+prefix[i][j-1]-prefix[i-1][j-1];
        }
    for (int x1 = 1; x1 <= n-1; ++x1) {
        for (int y1 = 1; y1 <= n-1; ++y1) {
            for (int x2 = x1+1; x2 <= n; ++x2) {
                for (int y2 = y1+1; y2 <= n; ++y2) {
                    ans = max(prefix[x2][y2]-prefix[x2][y1-1]-prefix[x1-1][y2]+prefix[x1-1][y1-1], ans);
                }
            }
        }
    }
    printf("%d\n", ans);
    return 0;
}

二维的 最大区域中点的个数

https://www.luogu.com.cn/problem/P1369

题目：计算一个矩形区域内的最多的点数

=》等价转换为一个区域内，有点的地方计为1，没点的地方计0，然后求区域和的最大值

思路：维护一个前缀和数组，然后直接通过遍历两个维度的起点和终点，然后利用前缀和数组来构造出矩形的边上的值的和。

对于区域的，右下角的减去左下减去右上再加上左上。因为左上那个区域被剪了两次。

#include <iostream>
using namespace std;
#define maxn 125
int n, ta, tb, prefix[maxn][maxn], ans=0;

int main() {
    scanf("%d", &n);
    for (int i = 1; i <= n; ++i) {
        scanf("%d%d", &ta, &tb);
        prefix[ta][tb] += 1;
    }
    n=100;
    for (int i = 1; i <= n; ++i)
        for (int j = 1; j <= n; ++j)
            prefix[i][j] += prefix[i-1][j]+prefix[i][j-1]-prefix[i-1][j-1];
    for (int x1 = 1; x1 <= n-1; ++x1) {
        for (int y1 = 1; y1 <= n-1; ++y1) {
            for (int x2 = x1+1; x2 <= n; ++x2) {
                for (int y2 = y1+1; y2 <= n; ++y2) {
                    int ot = prefix[x2][y2]-prefix[x1-1][y2]-prefix[x2][y1-1]+prefix[x1-1][y1-1];
                    int it = prefix[x2-1][y2-1]-prefix[x1][y2-1]-prefix[x2-1][y1]+prefix[x1][y1];
                    ans = max(ot-it, ans);
                }
            }
        }
    }
    printf("%d\n", ans);
    return 0;
}

二维的 区域矩阵覆盖+单点最大

https://www.luogu.com.cn/problem/P3397

题目大意：区域盖毯子，每个点上可以叠上多个毯子，问叠的毯子最多的点所叠的个数

1、差分就是和前缀和互逆的过程

#include <iostream>
using namespace std;
#define maxn 1005
int n, m, diff[maxn][maxn], bgx, bgy, edx, edy;

int main() {
    scanf("%d%d", &n, &m);
    while (m--) {
        scanf("%d%d%d%d", &bgx, &bgy, &edx, &edy);
        for (int i = bgx; i <= edx; ++i) diff[i][bgy]++,diff[i][edy+1]--;
    }
    for (int i = 1; i <= n; ++i) {
        for (int j = 1; j <= n; ++j) {
            diff[i][j] += diff[i][j-1];
            printf("%d ", diff[i][j]);
        }
        printf("\n");
    }
    return 0;
}

二维的 最大正方形

https://www.luogu.com.cn/problem/P1387

题目大意：给出01矩阵，求最大的正方形。

dp：状态转移方程为dp[i][j] = min(dp[i][j-1], dp[i-1][j], dp[i-1][j-1]);(注意这里只是伪代码，要运行需要min套min)

#include <iostream>
using namespace std;
#define maxn 105
int n, m, a[maxn][maxn], dp[maxn][maxn], ans;
#include <cmath>
// dp[i][j] = min(dp[i-1][j-1], dp[i][j-1], dp[i-1][j])+1;

int main() {
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= n; ++i)
        for (int j = 1; j <= m; ++j)
            scanf("%d", &a[i][j]);
    for (int i = 1; i <= n; ++i)
        for (int j = 1; j <= m; ++j)
            if (a[i][j]) dp[i][j] = min(min(dp[i-1][j-1], dp[i][j-1]), dp[i-1][j])+1;
    for (int i = 1; i <= n; ++i)
        for (int j = 1; j <= m; ++j)
            ans = max(ans, dp[i][j]);
    printf("%d\n", ans);
    return 0;
}
Posted on Feb 1, 2021