Sponsored
This approach involves preprocessing the matrix to build a prefix sum array. The prefix sum at any index (i, j) in this array contains the sum of elements from (0, 0) to (i, j). With this preprocessed information, calculating any submatrix sum becomes feasible in constant time using the inclusion-exclusion principle.
For a query with corners (row1, col1) and (row2, col2), compute the sum using:
Time Complexity: O(m * n) for construction, O(1) for each query.
Space Complexity: O(m * n) for the prefix sum storage.
1public class NumMatrix {
2 private int[,] sum;
3
4 public NumMatrix(int[][] matrix) {
5 int m = matrix.Length;
6 int n = matrix[0].Length;
7 sum = new int[m + 1, n + 1];
8
9 for (int i = 1; i <= m; i++) {
10 for (int j = 1; j <= n; j++) {
11 sum[i, j] = matrix[i - 1][j - 1] + sum[i - 1, j] + sum[i, j - 1] - sum[i - 1, j - 1];
12 }
13 }
14 }
15
16 public int SumRegion(int row1, int col1, int row2, int col2) {
17 return sum[row2 + 1, col2 + 1] - sum[row2 + 1, col1] - sum[row1, col2 + 1] + sum[row1, col1];
18 }
19}C# uses a 2D array to precompute sums for O(1) query calculations.
This approach involves using a 2D Fenwick Tree to update and query the matrix sums efficiently. Fenwick Trees provide a structure that allows for querying prefix sums, updating values, and hence facilitating the calculation of region sums after updates.
Time Complexity: O(log m * log n) per update or query.
Space Complexity: O(m * n) for the tree structure.
1#include <vector>
2using namespace std;
3
4class NumMatrix {
5public:
6 int m, n;
vector<vector<int>> tree;
vector<vector<int>> nums;
NumMatrix(vector<vector<int>>& matrix) {
m = matrix.size();
n = matrix[0].size();
tree.resize(m + 1, vector<int>(n + 1));
nums.resize(m, vector<int>(n));
for (int i = 0; i < m; ++i) {
for (int j = 0; j < n; ++j) {
update(i, j, matrix[i][j]);
}
}
}
void update(int row, int col, int val) {
int diff = val - nums[row][col];
nums[row][col] = val;
for (int i = row + 1; i <= m; i += i & -i) {
for (int j = col + 1; j <= n; j += j & -j) {
tree[i][j] += diff;
}
}
}
int sumRange(int row1, int col1, int row2, int col2) {
return sum(row2, col2) - sum(row2, col1 - 1) - sum(row1 - 1, col2) + sum(row1 - 1, col1 - 1);
}
private:
int sum(int row, int col) {
int total = 0;
for (int i = row + 1; i > 0; i -= i & -i) {
for (int j = col + 1; j > 0; j -= j & -j) {
total += tree[i][j];
}
}
return total;
}
};This C++ solution makes use of a 2D Fenwick Tree which is efficient for both point updates and querying prefix sums, making it feasible to handle dynamic updation scenarios.