304. Range Sum Query 2D - Immutable

https://leetcode.com/problems/range-sum-query-2d-immutable/description/

Given a 2D matrix, find the sum of the elements inside the rectangle defined by its upper left corner (row1, col1) and lower right corner (row2, col2).

Range Sum Query 2D

The above rectangle (with the red border) is defined by (row1, col1) = (2, 1) and (row2, col2) = (4, 3), which contains sum = 8.

Thoughts

不可变二维矩阵，实现API用来求它内部由参数决定边界的长方块的和。二维presum思想，presum[i][j]存从[0, 0]到[i, j]元素的和，求长方块的和时让右下角的presum减去上面和左边不在范围内的，最后再加上被重复删除的部分，也就是重叠的部分。

Code

class NumMatrix {
public:
    vector<vector<int>> presum;
    NumMatrix(vector<vector<int>>& matrix) {
        const int M = matrix.size(), N = M == 0 ? 0 : matrix[0].size();
        presum.resize(M, vector<int>(N, 0));
        for (int j = 0; j < N; ++j) {
            for (int i = 0, s = 0; i < M; ++i) {
                presum[i][j] = matrix[i][j];
                if (i > 0) presum[i][j] += presum[i - 1][j];
                if (j > 0) presum[i][j] += presum[i][j - 1];
                if (i > 0 && j > 0) presum[i][j] -= presum[i - 1][j - 1];
            }
        }
    }
    
    int sumRegion(int row1, int col1, int row2, int col2) {
        const auto up = col1 > 0 ? presum[row2][col1 - 1] : 0, left = row1 > 0 ? presum[row1 - 1][col2] : 0, overlap = col1 > 0 && row1 > 0 ? presum[row1 - 1][col1 - 1] : 0;
        return presum[row2][col2] - up - left + overlap;
    }
};

/**
 * Your NumMatrix object will be instantiated and called as such:
 * NumMatrix* obj = new NumMatrix(matrix);
 * int param_1 = obj->sumRegion(row1,col1,row2,col2);
 */

class NumMatrix {
    int[][] f;

    public NumMatrix(int[][] matrix) {
        int m = matrix.length;
        if (m == 0) {
            return;
        }
        int n = matrix[0].length;
        f = new int[m][n];
        f[0][0] = matrix[0][0];
        for (int i = 1; i < m; i++) {
            f[i][0] = f[i - 1][0] + matrix[i][0];
        }
        for (int j = 1; j < n; j++) {
            f[0][j] = f[0][j - 1] + matrix[0][j];
        }
        for (int i = 1; i < m; i++) {
            for (int j = 1; j < n; j++) {
                f[i][j] = f[i - 1][j] + f[i][j - 1] - f[i - 1][j - 1] + matrix[i][j];
            }
        }
    }

    public int sumRegion(int row1, int col1, int row2, int col2) {
        int sum = f[row2][col2];
        //System.out.println(sum);

        if (row1 > 0) {
            sum -= f[row1 - 1][col2];
            //System.out.println("1:" + f[row1 - 1][col2]);
        }
        if (col1 > 0) {
            sum -= f[row2][col1 - 1];
            //System.out.println("2:" + f[row2][col1 - 1]);
        }
        if (row1 > 0 && col1 > 0) {
            sum += f[row1 - 1][col1 - 1];
        }
        return sum; 
    }
}

/**
 * Your NumMatrix object will be instantiated and called as such:
 * NumMatrix obj = new NumMatrix(matrix);
 * int param_1 = obj.sumRegion(row1,col1,row2,col2);
 */

Analysis

Errors:

1. if (row1 > 0 && col1 > 0) {

          sum += f\[row1 - 1\]\[col1 - 1\];
   
      }没写

时间复杂度为O(mn).