一维矩阵中的前缀和

例题

给定一个整数数组  nums，处理以下类型的多个查询:

  1. 计算索引 left 和 right （包含 left 和 right）之间的 nums 元素的 和 ，其中 left <= right

实现 NumArray 类：

  • NumArray(int[] nums) 使用数组 nums 初始化对象
  • int sumRange(int i, int j) 返回数组 nums 中索引 left 和 right 之间的元素的 总和 ，包含 left 和 right 两点（也就是 nums[left] + nums[left + 1] + ... + nums[right] )

示例 1：

输入：
[“NumArray”, “sumRange”, “sumRange”, “sumRange”]
[[[-2, 0, 3, -5, 2, -1]], [0, 2], [2, 5], [0, 5]]
输出：
[null, 1, -1, -3]

解释：
NumArray numArray = new NumArray([-2, 0, 3, -5, 2, -1]);
numArray.sumRange(0, 2); // return 1 ((-2) + 0 + 3)
numArray.sumRange(2, 5); // return -1 (3 + (-5) + 2 + (-1))
numArray.sumRange(0, 5); // return -3 ((-2) + 0 + 3 + (-5) + 2 + (-1))

提示：

  • 1 <= nums.length <= 104
  • -105 <= nums[i] <= 105
  • 0 <= i <= j < nums.length
  • 最多调用 104 次 sumRange 方法

题目来源：力扣 303. 区域和检索 - 数组不可变。

最笨的解法：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class NumArray {
	private int[] nums;
	public NumArray(int[] nums) {
		this.nums = nums;
	}

	public int sumRange(int left, int right) {
		// 用 for 循环遍历求和
		int sum = 0;
		for (int i = left; i <= right; i++) {
			sum += nums[i];
		}
		return sum;
	}
}

这个解法每次调用 sumRange 函数时，都要进行一次 for 循环遍历，时间复杂度为 O(N)O(N)，而 sumRange 的调用频率可能非常高，所以这个算法的效率很低。

核心思路

前缀和数组的核心思路是通过预处理来优化区间和查询的效率。

基本思想

  1. 预先计算前缀和：创建一个新数组 prefix，其中 prefix[i] 表示原数组 nums 从索引 0 到 i 的所有元素之和

    • prefix[0] = nums[0]
    • prefix[1] = nums[0] + nums[1]
    • prefix[i] = nums[0] + nums[1] + ... + nums[i]

  2. 数学关系：任意区间 [left, right] 的和可以通过前缀和数组快速计算：

    • sumRange(left, right) = prefix[right] - prefix[left-1]
    • 当 left = 0 时，直接返回 prefix[right]

实现示例

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class NumArray {
private:
    vector<int> prefix;
    
public:
    NumArray(vector<int>& nums) {
        prefix.resize(nums.size()); ## 首先需要让prefix数组和nums一样大
        prefix[0] = nums[0];
        for (int i = 1; i < nums.size(); i++) {
            prefix[i] = prefix[i-1] + nums[i];
        }
    }
    
    int sumRange(int left, int right) {
        if (left == 0) {
            return prefix[right];
        }
        return prefix[right] - prefix[left-1];
    }
};

优势分析

  • 时间复杂度：
    • 预处理：O(n)
    • 每次查询：O(1)
  • 空间复杂度：O(n)

相比暴力解法的 O(n) 查询时间，前缀和数组将多次查询的时间复杂度从 O(k×n) 优化到 O(n+k)，其中 k 是查询次数，这在频繁查询的场景下效率提升显著。

二维矩阵中的前缀和

例题

给定一个二维矩阵 matrix，以下类型的多个请求：

  • 计算其子矩形范围内元素的总和，该子矩阵的 左上角 为 (row1, col1) ，右下角 为 (row2, col2) 。

实现 NumMatrix 类：

  • NumMatrix(int[][] matrix) 给定整数矩阵 matrix 进行初始化
  • int sumRegion(int row1, int col1, int row2, int col2) 返回 左上角 (row1, col1) 、右下角 (row2, col2) 所描述的子矩阵的元素 总和 。

示例 1：

输入:
[“NumMatrix”,“sumRegion”,“sumRegion”,“sumRegion”]
[[[[3,0,1,4,2],[5,6,3,2,1],[1,2,0,1,5],[4,1,0,1,7],[1,0,3,0,5]]],[2,1,4,3],[1,1,2,2],[1,2,2,4]]
输出:
[null, 8, 11, 12]

解释:
NumMatrix numMatrix = new NumMatrix([[3,0,1,4,2],[5,6,3,2,1],[1,2,0,1,5],[4,1,0,1,7],[1,0,3,0,5]]);
numMatrix.sumRegion(2, 1, 4, 3); // return 8 (红色矩形框的元素总和)
numMatrix.sumRegion(1, 1, 2, 2); // return 11 (绿色矩形框的元素总和)
numMatrix.sumRegion(1, 2, 2, 4); // return 12 (蓝色矩形框的元素总和)

提示：

  • m == matrix.length
  • n == matrix[i].length
  • 1 <= m, n <= 200
  • -105 <= matrix[i][j] <= 105
  • 0 <= row1 <= row2 < m
  • 0 <= col1 <= col2 < n
  • 最多调用 104 次 sumRegion 方法

题目来源：力扣 304. 二维区域和检索 - 矩阵不可变。

同理，子矩阵的元素和可以转化为周边几个以原点为七点的大矩阵的元素和的运算

那么做这道题的思路和一维数组中的前缀和是非常类似的，我们可以维护一个二维 preSum 数组，专门记录以原点为顶点的矩阵的元素之和，就可以用几次加减运算算出任何一个子矩阵的元素和。

二维矩阵中的前缀和核心思想是将一维前缀和的概念扩展到二维空间，通过预处理来快速计算任意子矩阵的元素和。

基本思想

  1. 定义二维前缀和数组：

    • 创建 preSum[i+1][j+1] 表示从 (0,0) 到 (i,j) 的矩形区域元素总和
    • 使用 i+1 和 j+1 是为了避免边界条件判断

  2. 前缀和计算公式：

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

  3. 子矩阵和计算公式：

    • 对于子矩阵 (row1, col1) 到 (row2, col2)：
    1
    sum = preSum[row2+1][col2+1] - preSum[row1][col2+1] - preSum[row2+1][col1] + preSum[row1][col1]

实现示例

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class NumMatrix {
private:
    vector<vector<int>> preSum;
    
public:
    NumMatrix(vector<vector<int>>& matrix) {
        int m = matrix.size(), n = matrix[0].size();
        if(m==0 || n==0 ) return;
        preSum.resize(m+1, vector<int>(n+1, 0));
        
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                preSum[i+1][j+1] = preSum[i][j+1] + preSum[i+1][j] 
                                  - preSum[i][j] + matrix[i][j];
            }
        }
    }
    
    int sumRegion(int row1, int col1, int row2, int col2) {
        return preSum[row2+1][col2+1] - preSum[row1][col2+1] 
               - preSum[row2+1][col1] + preSum[row1][col1];
    }
};

几何解释

如图所示，任意子矩阵的和可以通过四个以原点为顶点的大矩阵的加减运算得到：

  • preSum[row2+1][col2+1]：整个大矩形
  • 减去 preSum[row1][col2+1]：上方的矩形
  • 减去 preSum[row2+1][col1]：左侧的矩形
  • 加上 preSum[row1][col1]：被重复减去的左上角小矩形

优势分析

  • 时间复杂度：
    • 预处理：O(m×n)
    • 每次查询：O(1)
  • 空间复杂度：O(m×n)

相比暴力解法的 O(k×m×n) 查询时间（k 为查询次数），二维前缀和将多次查询的时间复杂度优化到 O(m×n+k)，在频繁查询子矩阵和的场景下效率提升显著。