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.
1#include <stdlib.h>
2
3typedef struct {
4 int** sum;
5 int nrows;
6 int ncols;
7} NumMatrix;
8
9NumMatrix* numMatrixCreate(int** matrix, int matrixSize, int* matrixColSize) {
10 NumMatrix* obj = (NumMatrix*) malloc(sizeof(NumMatrix));
11 obj->nrows = matrixSize;
12 obj->ncols = matrixColSize[0];
13
14 obj->sum = (int**) malloc((obj->nrows + 1) * sizeof(int*));
15 for(int i = 0; i <= obj->nrows; i++) {
16 obj->sum[i] = (int*) malloc((obj->ncols + 1) * sizeof(int));
17 for(int j = 0; j <= obj->ncols; j++) {
18 obj->sum[i][j] = 0;
19 }
20 }
21
22 for(int i = 1; i <= obj->nrows; i++) {
23 for(int j = 1; j <= obj->ncols; j++) {
24 obj->sum[i][j] = matrix[i-1][j-1] + obj->sum[i-1][j] + obj->sum[i][j-1] - obj->sum[i-1][j-1];
25 }
26 }
27
28 return obj;
29}
30
31int numMatrixSumRegion(NumMatrix* obj, int row1, int col1, int row2, int col2) {
32 return obj->sum[row2+1][col2+1] - obj->sum[row2+1][col1] - obj->sum[row1][col2+1] + obj->sum[row1][col1];
33}
34
35void numMatrixFree(NumMatrix* obj) {
36 for(int i = 0; i <= obj->nrows; i++) {
37 free(obj->sum[i]);
38 }
39 free(obj->sum);
40 free(obj);
41}In the C implementation, a 2D prefix sum array is created during initialization. The sum is calculated by adding and subtracting precomputed values from this 2D array.
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.