子矩阵的和

子矩阵的和

输入一个 n 行 m 列的整数矩阵，再输入 q 个询问，每个询问包含四个整数 x1, y1, x2, y2，表示一个子矩阵的左上角坐标和右下角坐标。对于每个询问，输出子矩阵中所有数的和。

所用方法和基本原理

1. 二维前缀和数组构建：
   • 定义了 getPrefixSum 方法用于生成二维前缀和数组 s。二维前缀和数组 s[i][j] 代表从矩阵左上角 (0, 0) 到位置 (i, j) 所构成子矩阵的元素总和。
   • 初始化 s[0][0] = 0，因为空矩阵的元素和为 0。
   • 通过两层嵌套循环遍历原矩阵 arr。对于每个位置 (i, j)，利用公式 s[i][j] = s[i - 1][j] + s[i][j - 1] - s[i - 1][j - 1] + arr[i][j] 来计算前缀和。这里，s[i - 1][j] 是上方子矩阵的和，s[i][j - 1] 是左方子矩阵的和，由于这两个子矩阵有重叠部分（左上角为 (i - 1, j - 1) 的子矩阵），所以要减去 s[i - 1][j - 1]，再加上当前位置的元素 arr[i][j]，从而得到从 (0, 0) 到 (i, j) 的子矩阵的元素总和。
2. 子矩阵和计算：
   • 对于每个询问给出的子矩阵 (x1, y1, x2, y2)，借助已构建的二维前缀和数组 s 计算其和。计算公式为 s[x2][y2] - s[x1 - 1][y2] - s[x2][y1 - 1] + s[x1 - 1][y1 - 1]。
   • s[x2][y2] 是从矩阵左上角 (0, 0) 到右下角 (x2, y2) 的子矩阵的和。减去 s[x1 - 1][y2] 可去掉所求子矩阵左边部分的和，减去 s[x2][y1 - 1] 可去掉所求子矩阵上边部分的和。但这样会多减去一次左上角为 (x1 - 1, y1 - 1) 的子矩阵（即重叠部分），所以要加上 s[x1 - 1][y1 - 1]，最终得到以 (x1, y1) 为左上角、(x2, y2) 为右下角的子矩阵的和。

代码及注释

import java.util.Scanner;

public class SubMatrixSum {
    // 生成二维前缀和数组
    public static int[][] getPrefixSum(int[][] arr) {
        int[][] s = new int[arr.length + 1][arr[0].length + 1];
        for (int i = 1; i <= arr.length; i++) {
            for (int j = 1; j <= arr[0].length; j++) {
                s[i][j] = s[i - 1][j] + s[i][j - 1] - s[i - 1][j - 1] + arr[i - 1][j - 1];
            }
        }
        return s;
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int m = sc.nextInt();
        int[][] arr = new int[n][m];
        // 输入矩阵元素
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                arr[i][j] = sc.nextInt();
            }
        }
        int q = sc.nextInt();
        int[][] s = getPrefixSum(arr);
        // 处理每个查询
        for (int i = 0; i < q; i++) {
            int x1 = sc.nextInt();
            int y1 = sc.nextInt();
            int x2 = sc.nextInt();
            int y2 = sc.nextInt();
            // 计算并输出子矩阵的和
            System.out.println(s[x2][y2] - s[x1 - 1][y2] - s[x2][y1 - 1] + s[x1 - 1][y1 - 1]);
        }
        sc.close();
    }
}

举例说明

假设有一个 3×3 的矩阵，实际构建前缀和数组时按 4×4 处理（多一行一列用于边界处理，值都为 0）：
原矩阵 arr：

1. 构建二维前缀和数组：

   • 初始化 s 为 4×4 的数组，所有元素初始值为 0。
   • 计算前缀和：
     • s[1][1] = s[0][1] + s[1][0] - s[0][0] + arr[0][0] = 0 + 0 - 0 + 1 = 1
     • s[1][2] = s[0][2] + s[1][1] - s[0][1] + arr[0][1] = 0 + 1 - 0 + 2 = 3
     • s[1][3] = s[0][3] + s[1][2] - s[0][2] + arr[0][2] = 0 + 3 - 0 + 3 = 6
     • s[2][1] = s[1][1] + s[2][0] - s[1][0] + arr[1][0] = 1 + 0 - 0 + 4 = 5
     • s[2][2] = s[1][2] + s[2][1] - s[1][1] + arr[1][1] = 3 + 5 - 1 + 5 = 12
     • s[2][3] = s[1][3] + s[2][2] - s[1][2] + arr[1][2] = 6 + 12 - 3 + 6 = 21
     • s[3][1] = s[2][1] + s[3][0] - s[2][0] + arr[2][0] = 5 + 0 - 0 + 7 = 12
     • s[3][2] = s[2][2] + s[3][1] - s[2][1] + arr[2][1] = 12 + 12 - 5 + 8 = 27
     • s[3][3] = s[2][3] + s[3][2] - s[2][2] + arr[2][2] = 21 + 27 - 12 + 9 = 45

   二维前缀和数组 s 为：

   	0	0	0	0
   	0	1	3	6
   	0	5	12	21
   	0	12	27	45

2. 计算查询的子矩阵和：

   • 对于查询 (1, 1, 2, 2)，x1 = 1，y1 = 1，x2 = 2，y2 = 2。
   • s[x2][y2] - s[x1 - 1][y2] - s[x2][y1 - 1] + s[x1 - 1][y1 - 1] = s[2][2] - s[0][2] - s[2][0] + s[0][0] = 12 - 0 - 0 + 0 = 12

方法的优劣

1. 时间复杂度：
   • 预处理阶段：构建二维前缀和数组时，有两层嵌套循环，每层循环的次数分别为 n + 1 和 m + 1，时间复杂度为 $O((n+1)\times (m+1))$，简化后为 $O(n\times m)$，其中 n 是矩阵的行数，m 是矩阵的列数。
   • 查询阶段：对于 q 个查询，每个查询只需进行固定次数的数组访问和加减法运算，时间复杂度为 $O(1)$，因此查询阶段的总时间复杂度为 $O(q)$。综合来看，整体时间复杂度为 $O(n\times m+q)$。相较于每次查询都遍历子矩阵所有元素的暴力解法（时间复杂度为 $O(q\times n\times m)$），此方法在处理多个查询时效率大幅提高。
2. 空间复杂度：
   需要额外创建一个 (n + 1)×(m + 1) 的二维数组 s 来存储前缀和，所以空间复杂度为 $O((n+1)\times (m+1))$，简化后为 $O(n\times m)$。

优点：
- 对于多个子矩阵和的查询操作，效率很高，能够快速得出结果。
- 算法思路明确，基于二维前缀和的计算逻辑相对容易理解和实现。

缺点：
- 空间开销较大，需要额外的空间来存储前缀和数组，在处理大规模矩阵时可能面临内存不足的问题。
- 如果矩阵元素频繁变动，每次变动后都需要重新计算二维前缀和数组，维护成本较高。