Given a 2D matrix matrix, find the sum of the elements inside the rectangle defined by its upper left corner (row1, col1) and lower right corner (row2, col2).
Example:
Given 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
Note:
前面一个博文的衍生版本，由原来的一维矩阵变成了现在的二维矩阵，没什么区别，还是先建立和的数组，代码如下所示：
1 class NumMatrix { 2 public: 3 NumMatrix(vector<vector<int>> &matrix){ 4 if(!matrix.size() || !matrix[0].size()) 5 return; 6 sum = vector<vector<int>>(matrix.size(), vector<int>(matrix[0].size(), 0)); 7 for(int i = 0; i < matrix.size(); ++i){ 8 for(int j = 0; j < matrix[0].size(); ++j){ 9 if(i != 0 && j != 0){ 10 sum[i][j] = matrix[i][j] + sum[i][j-1] + sum[i-1][j] - sum[i-1][j-1]; 11 }else if(i == 0 && j == 0){ 12 sum[i][j] = matrix[i][j]; 13 }else if(i == 0){ 14 sum[i][j] = matrix[i][j] + sum[i][j-1]; 15 }else{ 16 sum[i][j] = matrix[i][j] + sum[i-1][j]; 17 } 18 } 19 } 20 } 21 22 int sumRegion(int row1, int col1, int row2, int col2) { 23 if(row1 == 0 && col1 == 0) 24 return sum[row2][col2]; 25 else if(row1 == 0) 26 return sum[row2][col2] - sum[row2][col1-1]; 27 else if(col1 == 0) 28 return sum[row2][col2] - sum[row1-1][col2]; 29 else 30 return sum[row2][col2] - sum[row2][col1-1] - sum[row1-1][col2] + sum[row1-1][col1-1]; 31 32 } 33 private: 34 vector<vector<int>> sum; 35 };
LeetCode OJ：Range Sum Query 2D - Immutable（区域和2D版本）
原文：http://www.cnblogs.com/-wang-cheng/p/4970948.html