Range Sum Query 2D - Mutable

Given a 2D matrix matrix, find the sum of the elements inside the rectangle defined by its upper left corner (row1, col1) and lower right corner (row2, col2).

Range Sum Query 2D - Mutable - 图1

The above rectangle (with the red border) is defined by (row1, col1) = (2, 1) and (row2, col2) = (4, 3), which contains sum = 8.

Example:

  1. Given matrix = [
  2.   [3, 0, 1, 4, 2],
  3.   [5, 6, 3, 2, 1],
  4.   [1, 2, 0, 1, 5],
  5.   [4, 1, 0, 1, 7],
  6.   [1, 0, 3, 0, 5]
  7. ]
  9. sumRegion(2, 1, 4, 3) -> 8
  10. update(3, 2, 2)
  11. sumRegion(2, 1, 4, 3) -> 10

Solution:

  1. public class NumMatrix {
  3.   int m, n;
  4.   int[][] arr;    // stores matrix[][]
  5.   int[][] BITree; // 2-D binary indexed tree
  7.   public NumMatrix(int[][] matrix) {
  8.     if (matrix.length == 0 || matrix[0].length == 0) {
  9.         return;
  10.     }
  12.     m = matrix.length;
  13.     n = matrix[0].length;
  15.     arr = new int[m][n];
  16.     BITree = new int[m + 1][n + 1];
  18.     for (int i = 0; i < m; i++) {
  19.       for (int j = 0; j < n; j++) {
  20.         update(i, j, matrix[i][j]); // init BITree[][]
  21.         arr[i][j] = matrix[i][j];   // init arr[][]
  22.       }
  23.     }
  24.   }
  26.   public void update(int i, int j, int val) {
  27.     int diff = val - arr[i][j];
  28.     arr[i][j] = val;
  30.     i++; j++;
  31.     while (i <= m) {
  32.       int k = j;
  33.       while (k <= n) {
  34.         BITree[i][k] += diff;
  35.         k += k & (-k);
  36.       }
  37.       i += i & (-i);
  38.     }
  39.   }
  41.   int getSum(int i, int j) {
  42.     int sum = 0;
  44.     i++; j++;
  45.     while (i > 0) {
  46.       int k = j;
  47.       while (k > 0) {
  48.         sum += BITree[i][k];
  49.         k -= k & (-k);
  50.       }
  51.       i -= i & (-i);
  52.     }
  53.     return sum;
  54.   }
  56.   public int sumRegion(int i1, int j1, int i2, int j2) {
  57.     return getSum(i2, j2) - getSum(i1-1, j2) - getSum(i2, j1-1) + getSum(i1-1, j1-1);
  58.   }
  59. }
  62. // Your NumMatrix object will be instantiated and called as such:
  63. // NumMatrix numMatrix = new NumMatrix(matrix);
  64. // numMatrix.sumRegion(0, 1, 2, 3);
  65. // numMatrix.update(1, 1, 10);
  66. // numMatrix.sumRegion(1, 2, 3, 4);