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


  • 3
    C

    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]);
        }
    };
    

Log in to reply
 

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