前缀和算法：一维与二维前缀和模板实现

查询时间复杂度：O(1)，预处理时间复杂度：O(N)。

1.2.2 Java 实现

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        int n = scan.nextInt();
        int q = scan.nextInt();
        // 为了防止溢出，用 long 类型的数组
        int[] arr = new int[n + 1];
        long[] dp = new long[n + 1];
        for (int i = 1; i <= n; i++) {
            arr[i] = scan.nextInt();
        }
        for (int i = 1; i <= n; i++) {
            dp[i] = dp[i - 1] + arr[i];
        }
        while (q > 0) {
            int l = scan.nextInt();
            int r = scan.nextInt();
            System.out.println(dp[r] - dp[l - 1]);
            q--;
        }
    }
}

查询时间复杂度：O(1)，预处理时间复杂度：O(N)。

1.3 思路推导

本题整个的思路、算法原理、解题过程建议在纸上推导一遍。自己能够推导很重要！

026【模板】二维前缀和

题目描述：

2.1 算法思路：前缀和

类比于一维数组的形式，如果我们能处理出来从 [0, 1] 位置到 [i, j] 位置这片区域内所有元素的累加和，就可以在 O(1) 的时间内，搞定矩阵内任意区域内所有元素的累加和。因此接下来仅需完成两步即可。

2.1.1 第一步：搞出来前缀和矩阵

这里就要用到一维数组里面的拓展知识，我们要在矩阵的最上面和最左边添加上一行和一列 0，这样我们就可以省去非常多的边界条件的处理。处理后的矩阵就像这样——

这样，我们填写前缀和矩阵数组的时候，下标直接从开始，能大胆使用 i－1，j－1 位置的值。

注意 dp 表与原数组 matrix 内的元素的映射关系：

（1）从 dp 表到 matrix 矩阵，横纵坐标减一； （2）从 matrix 矩阵到 dp 表，横纵坐标加一。

2.1.2 前缀和矩阵中 sum[i][j] 的含义，以及如何递推二维前缀和方程

1、sum[i][j] 的含义

sum[i][j] 表示，从 [0, 0] 位置到 [i, j] 位置这段区域内，所有元素的累加和。对应下图的红色区域：

2、递推方程

其实这个递推方程非常像我们小学做过求图形面积的题，我们可以将 [0, 0] 位置到 [i, j] 位置这段区域分解成下面的部分：

sum[i][j] = 红 + 蓝 + 绿 + 黄，分析一下这四块区域

（1）黄色部分最简单，它就是数组中的 matrix[i - 1][j - 1]（注意坐标的映射关系）；

（2）单独的蓝不好求，因为它不是我们定义的状态表示中的区域，同理，单独的绿也是；

（3）但是如果是红 + 蓝，正好是我们 dp 数组中 sum[i－1][j] 的值；

（4）同理，如果是红 + 绿，正好是我们 dp 数组中 sum[i][j - 1] 的值；

（5）如果把上面求的三个值加起来，那就是黄 + 红 + 蓝 + 红 + 绿，发现多算了一部分红的面积，因此再单独减去红的面积即可；

（6）红的面积正好也是符合 dp 数组的定义的，即 sum[i－1][j－1]。

综上所述，我们的递推方程就是——

sum[i][j] = sum[i - 1][j] + sum[i][j - 1] - sum[i - 1][j - 1] + matrix[i - 1][j - 1]

2.1.3 第二步：使用前缀和矩阵

题目的接口中提供的参数是原始矩阵的下标，为了避免下标映射错误，这里直接先把下标映射成 dp 表里面对应的下标——

row1++, col1++, row2++, col2++

接下来分析如何使用这个前缀和矩阵，如下图（注意这里的 row 和 col 都处理过了，对应的正是 sum 矩阵中的下标）：

对于左上角（row1，col1）、右下角（row2，col2) 围成的区域，正好是红色的部分。因此我们要求的就是红色部分的面积，继续分析几个区域：

（1）黄色，能直接求出来，就是 sum[row1－1, col1－1]（为什么减 1，因为要剔除掉 row 这一行和 col 这一列）；

（2）绿色，直接求不好求，但是和黄色拼起来，正好是 sum 表内 sum[row1 - 1][col2] 的数据；

（3）同理，蓝色不好求，但是蓝 + 黄 = sum[row2][col1－1]；

（4）再看看整个面积，好求嘛？非常好求，正好是 sum[row2][col2]；

（5）那么，红色就=整个面积 - 黄 - 绿 - 蓝，但是绿蓝不好求，我们可以这样减：整个面积 - (绿 + 黄) - (蓝 + 黄），这样相当于多减去了一个黄，再加上即可。

综上所述：红 = 整个面积 - (绿 + 黄) - (蓝 + 黄) + 黄，从而可得红色区域内的元素总和为——

sum[row2][col2] - sum[row2][col1 - 1] - sum[row1 - 1][col2] + sum[row1 - 1][col1 - 1]

2.2 算法实现

2.2.1 C++ 实现

#include <iostream>
#include <vector>
using namespace std;

int main() {
    // 1.读入数据
    int n = 0, m = 0, q = 0;
    cin >> n >> m >> q;
    vector<vector<int>> arr(n + 1, vector<int>(m + 1));
    for(int i = 1; i <= n; ++i)
        for(int j = 1; j <= m; j++) cin >> arr[i][j];

    // 2.预处理前缀和矩阵
    vector<vector<long long>> dp(n + 1, vector<long long>(m + 1));
    for(int i = 1; i <= n; i++)
        for(int j = 1; j <= m; j++)
            dp[i][j] = dp[i - 1][j] + dp[i][j - 1] + arr[i][j] - dp[i - 1][j - 1];

    // 3.使用前缀和矩阵
    int x1 = 0, y1 = 0, x2 = 0, y2 = 0;
    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;
}

查询时间复杂度：O(1)，预处理时间复杂度：O(N*M)。

2.2.2 Java 实现

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        int m = in.nextInt();
        int q = in.nextInt();
        int[][] arr = new int[n + 1][m + 1];
        long[][] dp = new long[n + 1][m + 1];

        // 读入数据
        for (int i = 1; i <= n; i++)
            for (int j = 1; j <= m; j++)
                arr[i][j] = in.nextInt();

        // 处理前缀和矩阵
        for (int i = 1; i <= n; i++)
            for (int j = 1; j <= m; j++)
                dp[i][j] = dp[i - 1][j] + dp[i][j - 1] - dp[i - 1][j - 1] + arr[i][j];

        // 使用前缀和矩阵
        while (q > 0) {
            int x1 = in.nextInt(), y1 = in.nextInt(), x2 = in.nextInt(), y2 = in.nextInt();
            System.out.println(dp[x2][y2] - dp[x1 - 1][y2] - dp[x2][y1 - 1] + dp[x1 - 1][y1 - 1]);
            q--;
        }
    }
}

查询时间复杂度：O(1)，预处理时间复杂度：O(N*M)。

2.3 思路推导

本题整个的思路、算法原理、解题过程建议在纸上推导一遍。自己能够推导很重要！