题解 | #【模板】二维前缀和#

题目链接

题目描述

给定一个由 $n \times m$ 个整数组成的矩阵 $A$ （下标均从 $1$ 开始）。现有 $q$ 次独立查询，第 $k$ 次查询给定四个整数 $x_1, y_1, x_2, y_2$ ，表示子矩阵的左上角坐标 $(x_1, y_1)$ 与右下角坐标 $(x_2, y_2)$ 。请你计算该子矩阵中全部元素之和，并依次回答所有查询。

解题思路

本题要求对一个固定的二维矩阵进行多次子矩阵求和。如果每次查询都通过双重循环遍历子矩阵内的所有元素，单次查询的时间复杂度为 $O(n \cdot m)$ ，总复杂度将达到 $O(n \cdot m \cdot q)$ ，这在数据量较大时是不可接受的。

类似于一维数组的区间求和问题，我们可以将前缀和的思想扩展到二维空间来解决。

1. 构建二维前缀和矩阵

我们创建一个新的矩阵，称为二维前缀和矩阵，记为 $S$ 。 $S[i][j]$ 的值定义为以 $(1, 1)$ 为左上角，以 $(i, j)$ 为右下角的子矩阵中所有元素的和。

为了计算方便，我们通常让前缀和矩阵的尺寸比原矩阵大一圈（即 $(n+1) \times (m+1)$ ），并用 $0$ 初始化。

$S[i][j]$ 的递推公式基于容斥原理： $S[i][j] = A[i][j] + S[i-1][j] + S[i][j-1] - S[i-1][j-1]$

这个公式的含义是： $(i,j)$ 处的总和等于正上方的总和，加上正左方的总和，减去被重复计算的左上方的总和，最后加上当前位置 $A[i][j]$ 的值。

构建整个二维前缀和矩阵只需要一次遍历，时间复杂度为 $O(n \cdot m)$ 。

2. 子矩阵求和查询

利用构建好的二维前缀和矩阵，我们可以在 $O(1)$ 的时间内计算出任意子矩阵的和。

对于一个左上角为 $(x_1, y_1)$ ，右下角为 $(x_2, y_2)$ 的子矩阵，其元素之和同样可以通过容斥原理计算： $\text{Sum}(x_1, y_1, x_2, y_2) = S[x_2][y_2] - S[x_1-1][y_2] - S[x_2][y_1-1] + S[x_1-1][y_1-1]$

这个公式的含义是：

取右下角 $(x_2, y_2)$ 的前缀和 $S[x_2][y_2]$ （大矩形）。
减去其上方多余部分的前缀和 $S[x_1-1][y_2]$ 。
减去其左方多余部分的前缀和 $S[x_2][y_1-1]$ 。
由于左上角 $(x_1-1, y_1-1)$ 的区域被减了两次，所以需要加回来一次，即 $+ S[x_1-1][y_1-1]$ 。

这样，我们通过 $O(n \cdot m)$ 的预处理，将每次查询的复杂度降到了 $O(1)$ 。

代码

c++
java
python

#include <iostream>
#include <vector>

using namespace std;
using LL = long long;

int main() {
    int n, m, q;
    cin >> n >> m >> q;

    // 二维前缀和矩阵，大小为 (n+1)x(m+1)
    vector<vector<LL>> s(n + 1, vector<LL>(m + 1, 0));

    for (int i = 1; i <= n; ++i) {
        for (int j = 1; j <= m; ++j) {
            LL val;
            cin >> val;
            // 构建二维前缀和
            s[i][j] = val + s[i - 1][j] + s[i][j - 1] - s[i - 1][j - 1];
        }
    }

    for (int k = 0; k < q; ++k) {
        int x1, y1, x2, y2;
        cin >> x1 >> y1 >> x2 >> y2;
        // 使用容斥原理计算子矩阵和
        LL sum = s[x2][y2] - s[x1 - 1][y2] - s[x2][y1 - 1] + s[x1 - 1][y1 - 1];
        cout << sum << endl;
    }

    return 0;
}

import java.util.Scanner;

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

        long[][] s = new long[n + 1][m + 1];

        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= m; j++) {
                long val = sc.nextLong();
                s[i][j] = val + s[i - 1][j] + s[i][j - 1] - s[i - 1][j - 1];
            }
        }

        for (int k = 0; k < q; k++) {
            int x1 = sc.nextInt();
            int y1 = sc.nextInt();
            int x2 = sc.nextInt();
            int y2 = sc.nextInt();

            long sum = s[x2][y2] - s[x1 - 1][y2] - s[x2][y1 - 1] + s[x1 - 1][y1 - 1];
            System.out.println(sum);
        }
    }
}

def solve():
    n, m, q = map(int, input().split())

    # 二维前缀和矩阵
    s = [[0] * (m + 1) for _ in range(n + 1)]

    # 读取原始矩阵并构建前缀和
    for i in range(1, n + 1):
        row = list(map(int, input().split()))
        for j in range(1, m + 1):
            s[i][j] = row[j-1] + s[i-1][j] + s[i][j-1] - s[i-1][j-1]
    
    # 处理查询
    for _ in range(q):
        x1, y1, x2, y2 = map(int, input().split())
        sum_val = s[x2][y2] - s[x1-1][y2] - s[x2][y1-1] + s[x1-1][y1-1]
        print(sum_val)

solve()

算法及复杂度

算法：二维前缀和 (2D Prefix Sum)
时间复杂度： $O(n \cdot m + q)$ 。其中 $O(n \cdot m)$ 用于构建二维前缀和矩阵， $O(q)$ 用于回答 $q$ 次查询，每次查询 $O(1)$ 。
空间复杂度： $O(n \cdot m)$ ，用于存储二维前缀和矩阵。