C++ O(1)query solution


  • 0
    N
    class NumMatrix {
    public:
        NumMatrix(vector<vector<int>> &matrix) {
            if (matrix.size() == 0) return;
            f_ = vector<vector<int>>(matrix.size() + 5, vector<int>(matrix[0].size() + 5, 0));
            for (int i = 0; i < matrix.size(); i ++)
                for (int j = 0; j < matrix[0].size(); j ++)
                    f_[i + 1][j + 1] = f_[i][j + 1] + f_[i + 1][j] - f_[i][j] + matrix[i][j];
        }
    
        int sumRegion(int row1, int col1, int row2, int col2) {
            if (f_.size() == 0) return 0;
            return f_[row2 + 1][col2 + 1] - f_[row2 + 1][col1] - f_[row1][col2 + 1] + f_[row1][col1];
        }
        
    private:
        vector<vector<int>> f_;
    };

Log in to reply
 

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