public NumMatrix(int[][] matrix) {
if (matrix == null || matrix.length == 0) {
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
bit.update(i, j, matrix[i][j]);
public void update(int row, int col, int val) {
int diff = val - nums[row][col];
bit.update(row, col, diff);
public int sumRegion(int row1, int col1, int row2, int col2) {
return bit.query(row2 + 1, col2 + 1) - bit.query(row2 + 1, col1) - bit.query(row1, col2 + 1) + bit.query(row1, col1);
public BIT(int m, int n) {
sums = new int[m + 1][n + 1];
public void update(int row, int col, int val) {
for (int i = row + 1; i < sums.length; i += (i & -i)) {
for (int j = col + 1; j < sums[0].length; j += (j & -j)) {
public int query(int row, int col) {
for (int i = row; i > 0; i -= (i & -i)) {
for (int j = col; j > 0; j -= (j & -j)) {
* 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);