# 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).
>
> ## Notice
>
> 1.The matrix is only modifiable by the update function.\
> 2.You may assume the number of calls to update and sumRegion function is distributed evenly.\
> 3.You may assume that row1 ≤ row2 and col1 ≤ col2.
>
> **Example**
>
> ```
> Given matrix = [
>   [3, 0, 1, 4, 2],
>   [5, 6, 3, 2, 1],
>   [1, 2, 0, 1, 5],
>   [4, 1, 0, 1, 7],
>   [1, 0, 3, 0, 5]
> ]
>
> sumRegion(2, 1, 4, 3) -> 8
> update(3, 2, 2)
> sumRegion(2, 1, 4, 3) -> 10
> ```

这题应该用2d binary index tree 或者 2d segementation tree。

用 2d binary index tree 的写法：

2d binary index tree 不太容易想到，但是想通了，写起来很简单，比1d的多一层循环而已

```python
class NumMatrix(object):

    def __init__(self, matrix):
        """
        :type matrix: List[List[int]]
        """
        m, n = len(matrix), len(matrix[0])            # 这里偷懒没有判断是否为为空matrix
        self.BIT = [[0] * (n + 1) for _ in xrange(m + 1)]
        self.m = [[0] * n for _ in xrange(m)]
        for i, row in enumerate(matrix):
            for j, n in enumerate(row):
                self.update(i, j, n)


    def update(self, row, col, val):
        """
        :type row: int
        :type col: int
        :type val: int
        :rtype: void
        """
        delta = val - self.m[row][col]
        self.m[row][col] = val
        i = row + 1
        while i < len(self.BIT):
            j = col + 1
            while j < len(self.BIT[0]):
                self.BIT[i][j] += delta
                j += j & (-j)
            i += i & (-i)



    def sumRegion(self, row1, col1, row2, col2):
        """
        :type row1: int
        :type col1: int
        :type row2: int
        :type col2: int
        :rtype: int
        """
        return self.get2DSum(row2, col2) + self.get2DSum(row1 - 1, col1 - 1) \
               - self.get2DSum(row1 - 1, col2) - self.get2DSum(row2, col1 - 1)


    def get2DSum(self, row, col):
        sum, i = 0, row + 1
        while i > 0:
            j = col + 1
            while j > 0:
                sum += self.BIT[i][j]
                j -= j & (-j)
            i -= i & (-i)
        return sum    


# Your NumMatrix object will be instantiated and called as such:
# obj = NumMatrix(matrix)
# obj.update(row,col,val)
# param_2 = obj.sumRegion(row1,col1,row2,col2)
```
