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.
1class NumMatrix {
2 constructor(matrix) {
3 const m = matrix.length;
4 const n = matrix[0].length;
5 this.sum = Array.from({ length: m + 1 }, () => Array(n + 1).fill(0));
6 for (let i = 1; i <= m; i++) {
7 for (let j = 1; j <= n; j++) {
8 this.sum[i][j] = matrix[i - 1][j - 1] + this.sum[i - 1][j] + this.sum[i][j - 1] - this.sum[i - 1][j - 1];
9 }
10 }
11 }
12
13 sumRegion(row1, col1, row2, col2) {
14 return this.sum[row2 + 1][col2 + 1] - this.sum[row2 + 1][col1] - this.sum[row1][col2 + 1] + this.sum[row1][col1];
15 }
16}The JavaScript implementation involves constructing a 2D prefix sum array to enable constant time retrieval of region sums.
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.
1class NumMatrix {
2 private int[]
The Java implementation adopts a similar logic to the C++ solution, using a 2D Fenwick Tree to support dynamic updates and range sum queries.