前缀和与二维前缀和算法模板详解

26.【模板】二维前缀和

题目描述

给定一个 n 行 m 列的矩阵，进行 q 次查询，每次查询子矩阵区域内所有元素的累加和。

解法

算法思路

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

第一步：搞出来前缀和矩阵 在矩阵的最上面和最左边添加上一行和一列 0，省去边界条件的处理。下标直接从 1 开始，能大胆使用 i-1，j-1 位置的值。 注意：dp 表与原数组 matrix 内的元素的映射关系：从 dp 表到 matrix 矩阵，横纵坐标减一；从 matrix 矩阵到 dp 表，横纵坐标加一。

sum[i][j] 表示，从 [0, 0] 位置到 [i, j] 位置这段区域内，所有元素的累加和。 递推方程： sum[i][j] = sum[i-1][j] + sum[i][j-1] - sum[i-1][j-1] + matrix[i-1][j-1]

第二步：使用前缀和矩阵 题目的接口中提供的参数是原始矩阵的下标，为了避免下标映射错误，这里直接先把下标映射成 dp 表里面对应的下标：row1++, col1++, row2++, col2++。 对于左上角 (row1, col1)，右下角 (row2, col2) 围成的区域，利用容斥原理计算： 红 = 整个面积 - (绿 + 黄) - (蓝 + 黄) + 黄 从而可得红色区域内的元素总和为： sum[row2][col2] - sum[row2][col1 - 1] - sum[row1 - 1][col2] + sum[row1 - 1][col1 - 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] << '\n';
    }
    return 0;
}