2D BIT Solution

class NumMatrix:
    function init(matrix):
        this.m = matrix.length
        this.n = matrix[0].length if this.m > 0 else 0
        this.matrix = 2D array of size m x n, filled with 0
        this.tree = 2D array of size (m+1) x (n+1), filled with 0
        for i = 0 to this.m - 1:
            for j = 0 to this.n - 1:
                this.update(i, j, matrix[i][j])

    function update(row, col, val):
        delta = val - this.matrix[row][col]
        this.matrix[row][col] = val
        i = row + 1
        while i <= this.m:
            j = col + 1
            while j <= this.n:
                this.tree[i][j] += delta
                j += j & (-j)
            i += i & (-i)

    function _query(row, col):
        result = 0
        i = row
        while i > 0:
            j = col
            while j > 0:
                result += this.tree[i][j]
                j -= j & (-j)
            i -= i & (-i)
        return result

    function sumRegion(r1, c1, r2, c2):
        return (this._query(r2+1, c2+1) - this._query(r1, c2+1)
            - this._query(r2+1, c1) + this._query(r1, c1))