一维前缀和

303. 区域和检索 – 数组不可变

给定一个整数数组nums，求出数组从索引i到j（i ≤ j）范围内元素的总和，包含 i、j 两点。实现 NumArray类：

  • NumArray(int[] nums) 使用数组nums初始化对象
  • int sumRange(int i, int j) 返回数组nums从索引i 到j（i ≤ j）范围内元素的总和，包含 i、j 两点（也就是 sum(nums[i], nums[i + 1], ... , nums[j])）

示例

输入：
["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))

提示

  • 0 <= nums.length <= 104
  • -10^5 <= nums[i] <= 10^5
  • 0 <= i <= j < nums.length
  • 最多调用 10^4 次 sumRange 方法

分析

​ 由于是实现一个类，其可能会被多次调用，所以需要考虑性能问题。最朴素的方式是每次求和都遍历一次数组，但是可能会超时，使用前缀和能以时间复杂度O(1)解决问题。

构建前缀和

遍历原数组即可构建前缀和（从0号元素开始到当前元素的累计和）

求区间和

例如求区间[2,7]之间的和，用S0~7–S0~1即可，避免重复的遍历。

完整代码如下

class NumArray {
public:
    vector<int> sums;

    NumArray(vector<int>& nums) {
        int n = nums.size();
        sums.resize(n + 1);
        for (int i = 0; i < n; i++) {    //遍历数组，构建前缀和
            sums[i + 1] = sums[i] + nums[i];
        }
    }

    int sumRange(int i, int j) {
        return sums[j + 1] - sums[i];
    }
};

二位前缀和

304. 二维区域和检索 – 矩阵不可变

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

上图子矩阵左上角 (row1, col1) = (2, 1) ，右下角(row2, col2) = (4, 3)，该子矩形内元素的总和为 8。

示例

给定 matrix = [
  [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]
]

sumRegion(2, 1, 4, 3) -> 8
sumRegion(1, 1, 2, 2) -> 11
sumRegion(1, 2, 2, 4) -> 12

提示

  • 你可以假设矩阵不可变。
  • 会多次调用 sumRegion 方法。
  • 你可以假设 row1 ≤ row2 且 col1 ≤ col2 。

分析

​ 和上一题类似，最朴素的方法是直接遍历即可，但是同样会有性能问题，而且二维数值的遍历性能损失会更大，使用二维前缀和可以是时间复杂度降到O(1)。

构建二维前缀和

​ P点前缀和可表示为Sa+Sb+Sc+P，其可转化为较小的前缀和表达式SumB+SumC-SumA+P（Sa、Sb、Sc表示a、b、c三个区域中元素和；SumA、SumB、SumC表示ABC三点的前缀和）

区域求和

2d-strip-1

​ 点P1[col1][row1]到点P2[col2][row2]之间的区域元素和可表示为：SD = SP2-(SA+SB) - (SA+SC)+SA因为A部分元素和被减去了两次所以需要加上一次。又因为：

  • SA = SP1
  • SA+SB = SP[col2][row1-1]
  • SA+SC = SP[col1-1][row2]

所以P1、P2两点之间的元素和可以用表示为4个前缀和的和差关系，运算时间复杂度为O(1)

完整代码如下

class NumMatrix {
public:
    vector<vector<int>> sums;

    NumMatrix(vector<vector<int>>& matrix) {
        int m = matrix.size();
        if(m>0) {
            int n = matrix[0].size();
            sums.resize(m+1, vector<int>(n+1));
            for(int i = 0; i < m; i++) {
                for(int j = 0; j < n; j++) {
                    sums[i+1][j+1] = matrix[i][j]+ sums[i+1][j] + sums[i][j+1] - sums[i][j];
                }
            }
        }
    }

    int sumRegion(int row1, int col1, int row2, int col2) {
        return sums[row2+1][col2+1] - sums[row1][col2+1] - sums[row2+1][col1] + sums[row1][col1];
    }
};