[recommend for beginners]clean C++ implementation with detailed explanation


  • -1
    class NumMatrix {
        vector<vector<int>> sums;
        bool flag;
    public:
        NumMatrix(vector<vector<int>> &matrix) {
            if(matrix.size()==0)  { flag=true; return; };
            flag=false;
            int row=matrix.size(), col=matrix[0].size();
            sums.resize(row+1, vector<int>(col+1, 0));
            for(int i=1; i<=row; i++){
                for(int j=1; j<=col; j++){
                    sums[i][j]=sums[i-1][j]+sums[i][j-1]-sums[i-1][j-1]+matrix[i-1][j-1];
                }
            }
        }
    
        int sumRegion(int row1, int col1, int row2, int col2) {
            if(flag)  return 0;
            else  return sums[row2+1][col2+1]-(sums[row2+1][col1]+sums[row1][col2+1]-sums[row1][col1]);
        }
    };
    
    
    // Your NumMatrix object will be instantiated and called as such:
    // NumMatrix numMatrix(matrix);
    // numMatrix.sumRegion(0, 1, 2, 3);
    // numMatrix.sumRegion(1, 2, 3, 4);

  • 0
    2

    Here is the solution to the immutable case ...

    class NumArray {
        vector<int> bit;
        vector<int> NUMS;
    public:
        NumArray(vector<int> &nums) : NUMS(nums) {
            int size_nums = nums.size();
            bit.resize(size_nums + 1);
            for(int i = 0; i < size_nums; i++) {
                add(i, nums[i]);
            }
        }
    
        void update(int i, int val) {
            if(val != NUMS[i]){
                add(i, val - NUMS[i]);
                NUMS[i] = val;
            }
        }
    
        int sumRange(int i, int j) {
            return sum(j) - sum(i-1);
        }
        
        int last_bit(int i) {
            return i & (-i);
        }
        
        void add(int i, int val) {
            i++;
            while(i < bit.size()) {
                bit[i] += val;
                i += last_bit(i);
            }
        }
        
        int sum(int i) {
            i++;
            int sum = 0;
            while(i > 0) {
                sum += bit[i];
                i -= last_bit(i);
            }
            return sum;
        }
    };

Log in to reply
 

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