class NumMatrix { private: long tree[10005][10005]; int n, m; vector<vector<int>> matrix; public: int lowbit(int x) { return x & -x; } void modify(int x0, int y0, int val) { for (int x = x0; x <= m; x += lowbit(x)) { for (int y = y0; y <= n; y += lowbit(y)) { tree[x][y] += val; } } } long query(int row, int col) { long ret = 0; for (int x = row; x > 0; x -= lowbit(x)) { for (int y = col; y > 0; y -= lowbit(y)) { ret += tree[x][y]; } } return ret; } NumMatrix(vector<vector<int>>& matrix) { m = matrix.size(); if (m) n = matrix[0].size(); this->matrix = matrix; for (int i = 0; i < m; i++) { for (int j = 0; j < n; j++) { modify(i + 1, j + 1, matrix[i][j]); } } } void update(int row, int col, int val) { int pre = matrix[row][col]; modify(row + 1, col + 1, val - pre); matrix[row][col] = val; } int sumRegion(int row1, int col1, int row2, int col2) { long d = query(row2 + 1, col2 + 1); long a = query(row1, col1); long b = query(row2 + 1, col1); long c = query(row1, col2 + 1); return d - b - c + a; } }; /** * Your NumMatrix object will be instantiated and called as such: * NumMatrix* obj = new NumMatrix(matrix); * obj->update(row,col,val); * int param_2 = obj->sumRegion(row1,col1,row2,col2); */