31 lines concise and easy understand c++ solution Binary Indexed Tree


  • 1
    A
    class NumMatrix {
    private:
        vector<vector<int>> sum;
        vector<vector<int>> origin;
        int m, n;
    public:
        NumMatrix(vector<vector<int>> &matrix) {
            if(matrix.size() == 0 || matrix[0].size() == 0) return;
            m = matrix.size(), n = matrix[0].size();
            sum = vector<vector<int>> (m + 1, vector<int>(n + 1, 0));
            origin = vector<vector<int>> (m, vector<int>(n, 0));
            for(int i = 0; i < m; i++){
                for(int j = 0; j < n; j++){
                    update(i, j, matrix[i][j]);
                }
            }
        }
    
        void update(int row, int col, int val) {
            int diff = val - origin[row][col];
            origin[row][col] = val;
            for(int i = row + 1; i <= m; i += (i & -i)){
                for(int j = col + 1; j <= n; j += (j & - j)){
                    sum[i][j] += diff;
                }
            }
        }
    
        int sumRegion(int row1, int col1, int row2, int col2) {
            if(m == 0 || n == 0) return 0;
            return getSum(row2 + 1, col2 + 1) + getSum(row1, col1) - getSum(row1, col2  + 1) - getSum(row2 + 1, col1);
        }
        
        int getSum(int row, int col){
            int res = 0;
            for(int i = row; i > 0; i -= (i & -i)){
                for(int j = col; j > 0; j -= (j & -j)){
                    res += sum[i][j];
                }
            }
            return res;
        }
    };
    
    
    // Your NumMatrix object will be instantiated and called as such:
    // NumMatrix numMatrix(matrix);
    // numMatrix.sumRegion(0, 1, 2, 3);
    // numMatrix.update(1, 1, 10);
    // numMatrix.sumRegion(1, 2, 3, 4);

  • 0
    S

    I like how you used update() in your constructor :). Good job.


Log in to reply
 

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