我爱学算法之—— 前缀和（上）

一、【模板】前缀和

题目解析

这道题，给定一个长度为n的数组，和m次询问； 每一次询问给出两个整数l和r，让我们求出区间[l , r]中所有数的和，然后输出。

算法思路

这道题暴力解法：

首先是m次查询（m次测试），每一个给定一个l和r，让我们求区间[l , r]中所有数的和。 暴力解法就非常简单了，直接遍历区间[l , r]，求出区间中所有数的和即可。

暴力解法时间复杂度O(m * n)，也就是O(n^2)级别的时间复杂度；

暴力解法会超时，我们这里想一想可不可以对暴力解法进行一些优化：

1. 首先m次查询，很显然是不能进行优化的。
2. 我们只能对求区间[l , r]中所有数的和进行优化。

那如何优化呢？

遍历区间[l , r]来求和时间复杂度是O(n)，那我们可不可以用O(1)的复杂度来获得区间[l , r]中所有数的和呢？

通过上图，我们可以发现：我们要求的[l , r]区间的和s就等于区间[1 , r]的和 减去区间[1 , l]的和。

前缀和

所以，我们可以通过运算来用O(1)的时间复杂度获得区间[l , r]中所有数的和；但是我们要用到区间[1 , l]和区间[1 , r]中所有数的和。 所以我们预先既要处理一个前缀和数组dp：

• 其中dp[i]：表示区间[1 , i]中所有数的和。
• 填写前缀和数组：dp[i] = dp[i-1] + arr[i]（也就是前面所有数的和加上当前位置的数）。
• 计算区间[l , r]中所有数的和：dp[r] - dp[l-1]（这里区间[l , r]包含l位置，所以要减去dp[i-1]。

这里可以说：前缀和和动态规划的大致思路非常相似： 状态表示：dp[i]表示区间[1 , i]中所有数的和 状态转移方程：dp[i] = dp[i] + arr[i]; 获取区间[l , r]中所有数的和：s = dp[r] - dp[l-1];

代码实现

#include <cmath>
#include <iostream>
using namespace std;
const int N = 100001;
long long dp[N];
int arr[N];
int n, m;
int main() {
    cin >> n >> m;
    for (int i = 1; i <= n; i++) {
        cin >> arr[i];
        dp[i] = dp[i - 1] + arr[i];
    }
    while (m--) {
        int l, r;
        cin >> l >> r;
        cout << dp[r] - dp[l - 1] << endl;
    }
    return 0;
}

二、【模板】二维前缀和

题目解析

对于这道题，给定一个n*m的二维数组，以及q次查询；

每一次查询给定x1,x2,y1,y2，我们要求以(x1,y1)为左上角，(x2,y2)为右下角的子矩阵中所有数的和。

算法思路

暴力解法：

q次查询，每一查询给定x1,y1,x2,y2，遍历整个子矩阵进行求和操作。

时间复杂度：O(n*m*q)，也就是O(n^3)级别的时间复杂度。

很显然会超时，对暴力解法进行优化，很显然只能优化求子矩阵中所有元素的和。

暴力解法中，遍历整个子矩阵去求和，这样太麻烦了；我们可不可以使用O(1)的时间复杂度拿到子矩阵中所有数的和？ 当然也是可以的，这就像数学当中求一块面积的和一样。

如上图所示，我们要求以(x1 , y1)为左上角，(x2 , y2)为右下角的子矩阵中所有数的和，也就是S；

我们只要知道s1（以(1 , 1)为左上角，(x1-1 , y1)为右下角的子矩阵的和）、s2（以(1 , 1)为左上角，(x2, y1-1)为右下角的子矩阵的和）、s3（以(1 , 1)为左上角，(x1-1 , y1-1)为右下角的子矩阵的和）以及s4（以(1 , 1)为左上角，(x2 , y2)为右下角的子矩阵的和）。

我们就可以通过数学运算来求S：s = s4 - s1 - s2 + s3。

也就是s = dp[x2][y2] - dp[x2][y1-1] - dp[x1-1][y2] + dp[x1-1][y1-1]

这样我们在填写前缀和表时：

dp[i][j] = dp[i][j-1] +dp[i-1][j] - dp[i-1][j-1] + arr[i][j]

这里也可以将前缀和理解为动态规划 状态表示：dp[i][j]表示以(1,1)为左上角，(i,j)为右下角的子矩阵中所有数的和。 状态转移方程：dp[i][j] = dp[i][j-1] +dp[i-1][j] - dp[i-1][j-1] + arr[i][j] 计算子矩阵中所有数的和：s = dp[x2][y2] - dp[x2][y1-1] - dp[x1-1][y2] + dp[x1-1][y1-1]

代码实现

#include <iostream>
using namespace std;
const int N = 1001;
int arr[N][N];
long long dp[N][N];
int n, m, q;
int x1, x2, y1, y2;

int main() {
    cin >> n >> m >> q;
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            cin >> arr[i][j];
            dp[i][j] = dp[i - 1][j] + dp[i][j - 1] - dp[i - 1][j - 1] + arr[i][j];
        }
    }
    while (q--) {
        cin >> x1 >> y1 >> x2 >> y2;
        cout << (dp[x2][y2] - dp[x1 - 1][y2] - dp[x2][y1 - 1] + dp[x1 - 1][y1 - 1]) << endl;
    }
    return 0;
}

总结

这里简单总结一下前缀和算法：

首先前缀和算法可以用来快速的求出子数组/子矩阵中所有数的和，在涉及到求子数组/子矩阵的和时，能够利用前缀和算法来快速的求和。 其次，使用前缀和，我们就要预先构建一个前缀和数组并填写该数组；（和动态规划类似） 注意：在构建前缀和数组时，通常下标从1开始，因为在填写数组时要用到dp[i-1] 最后，前缀和算法就是空间换时间，通过预先构建前缀和数组，让我们能够在O(1)的数据复杂度拿到子数组/子矩阵的和。

到这里本篇文章内容就结束了，感谢各位大佬的支持