## 思路

### 方法一

``````class NumMatrix {

int sum[][];

public NumMatrix(int[][] matrix) {
int r = matrix.length;
int c = matrix[0].length;
sum = new int[r][c+1];
for(int i = 0;i<r;i++){
for(int j = 0;j<c;j++){
sum[i][j+1] = sum[i][j]+matrix[i][j];
}
}
}

public int sumRegion(int row1, int col1, int row2, int col2) {
int ans = 0;
for(int i = row1;i<=row2;i++){
ans += sum[i][col2+1] - sum[i][col1];
}
return ans;
}
}

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

• 时间复杂度：O(mn)
• 空间复杂度：O(mn)

### 方法二

``````int n = matrix.length;
int m = matrix[0].length;
sum = new int[n + 1][m + 1];
// 预处理除前缀和数组（模板部分）
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) {
sum[i][j] = sum[i - 1][j] + sum[i][j - 1] - sum[i - 1][j - 1] + matrix[i - 1][j - 1];
}
}
``````

``````public int sumRegion(int x1, int y1, int x2, int y2) {
// 但由于我们源数组下标从 0 开始，因此要在模板的基础上进行 + 1
x1++; y1++; x2++; y2++;
return f[x2][y2] - f[x1 - 1][y2] - f[x2][y1 - 1] + f[x1 - 1][y1 - 1];
}
``````