Summed Area Table, a.k.a. Integral Image

• This is a well-studied problem and can be solved using a structure called Summed Area Table. This method is also known as Integral Image in Computer Vision. It has

• Space Complexity: O(M*N)
• Time Complexity for Range Sum Query: O(1)
• Time Complexity to Update a Value in Matrix: O(M*N)

For comparison, complexity of a naive approach which directly compute range sum from matrix is listed below.

• Space Complexity: O(1)
• Time Complexity for Range Sum Query: O(M*N)
• Time Complexity to Update a Value in Matrix: O(1)

An algorithm comes between them is called 2D Fenwick Tree (a.k.a. Binary Indexed Tree), which achieves log complexity for both range sum query and value update.

https://en.wikipedia.org/wiki/Summed_area_table

https://www.topcoder.com/community/data-science/data-science-tutorials/binary-indexed-trees/#2d

``````class NumMatrix {
public:
vector<vector<int>> sat;
bool empty=true;

NumMatrix(vector<vector<int>> &matrix) {
int row = matrix.size();
if(row == 0) return;
int col = matrix[0].size();
if(col == 0) return;
empty = false;

sat = vector<vector<int>>(row + 1, vector<int>(col + 1));

for(int i = 1; i <= row; i++)
for(int j = 1; j <= col; j++)
sat[i][j] = sat[i-1][j] + sat[i][j-1] - sat[i-1][j-1] + matrix[i-1][j-1];
}

int sumRegion(int row1, int col1, int row2, int col2) {
return empty? 0 : sat[row2+1][col2+1] - (sat[row2+1][col1] + sat[row1][col2+1] - sat[row1][col1]);
}
};
``````

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.