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, 20 insertions, 1 deletions
diff --git a/range_sum_query_2d.cpp b/range_sum_query_2d.cpp
index d50ea14..835354f 100644
--- a/range_sum_query_2d.cpp
+++ b/range_sum_query_2d.cpp
@@ -1,5 +1,14 @@
+// 304. Range Sum Query 2D - Immutable
#include "leetcode.h"
+/*
+ * given a 2d matrix 'matrix', handle multiple queries of the following type:
+ * calculate the sum of the elements of 'matrix' inside the rectangle defined by
+ * its upper left corner '(row1, col1)' and lower right corer '(row2, col2)'.
+ * you must design an algorithm where 'sumRegion' works on 'O(1)' time
+ * complexity.
+ */
+
class NumMatrix {
public:
vector<vector<int>> sum;
@@ -18,4 +27,14 @@ public:
}
};
-int main() {}
+int main() {
+ vvd(int) 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}};
+ NumMatrix *obj = new NumMatrix(matrix);
+ printf("%d\n", obj->sumRegion(2, 1, 4, 3)); // expect: 8
+ printf("%d\n", obj->sumRegion(1, 1, 2, 2)); // expect: 11
+ printf("%d\n", obj->sumRegion(1, 2, 2, 4)); // expect: 12
+}