2D BIT solution in C++(for practice), 284ms


  • 0
    S
    class NumMatrix {
    public:
    NumMatrix(vector<vector<int>> &matrix) {
        if (matrix.empty()) {
            return;
        }
        for (int i = 0; i <= matrix.size(); i++) {
            c.push_back(vector<int>(matrix[0].size() + 1, 0));
        }
        for (int i = 0; i < matrix.size(); i++) {
            for (int j = 0; j < matrix[0].size(); j++) {
                update(i + 1, j + 1, matrix[i][j]);
            }
        }
        
    }
    
    int sumRegion(int row1, int col1, int row2, int col2) {
        int a = read(row2 + 1, col2 + 1);
        int b = read(row2 + 1, col1);
        int c = read(row1, col2 + 1);
        int d = read(row1, col1);
        return a - b - c + d;
    }
    private:    
    vector<vector<int> > c;
    int lowbit(int x) {
        return x & (-x);
    }
    void update(int idi, int idj, int diff) {
        for (int i = idi; i < c.size(); i += lowbit(i)) {
            for (int j = idj; j < c[0].size(); j += lowbit(j)) {
                c[i][j] += diff;
            }
        }
    }
    int read(int idi, int idj) {
        int res = 0;
        for (int i = idi; i > 0; i -= lowbit(i)) {
            for (int j = idj; j > 0; j -= lowbit(j)) {
                res += c[i][j];
            }
        }
        return res;
    }
    };

Log in to reply
 

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