aboutsummaryrefslogtreecommitdiff
path: root/range_sum_query_2d.cpp
diff options
context:
space:
mode:
Diffstat (limited to 'range_sum_query_2d.cpp')
-rw-r--r--range_sum_query_2d.cpp21
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() {}