diff options
Diffstat (limited to 'range_sum_query_2d.cpp')
-rw-r--r-- | range_sum_query_2d.cpp | 21 |
1 files changed, 21 insertions, 0 deletions
diff --git a/range_sum_query_2d.cpp b/range_sum_query_2d.cpp new file mode 100644 index 0000000..d50ea14 --- /dev/null +++ b/range_sum_query_2d.cpp @@ -0,0 +1,21 @@ +#include "leetcode.h" + +class NumMatrix { +public: + vector<vector<int>> sum; + NumMatrix(vector<vector<int>> &matrix) { + int m = matrix.size(), n = matrix[0].size(); + sum = vector<vector<int>>(m + 1, vector<int>(n + 1)); + for (int i = 1; i <= m; i++) + for (int j = 1; j <= n; j++) + sum[i][j] = sum[i - 1][j] + sum[i][j - 1] - sum[i - 1][j - 1] + + matrix[i - 1][j - 1]; + } + int sumRegion(int row1, int col1, int row2, int col2) { + row1++, col1++, row2++, col2++; + return sum[row2][col2] - sum[row2][col1 - 1] - sum[row1 - 1][col2] + + sum[row1 - 1][col1 - 1]; + } +}; + +int main() {} |