[Google Question] Range Sum Query 2D with Updates

Problem: The problem is similar to our previous problem Range Sum Query 2D with an exception that we can update the given matrix so now we have to implement three methods:

• NumMatrix(int[][] matrix): Initializes the object with the 2D integer array matrix.
• int SumRegion(int row1, int col1, int row2, int col2): Return the sum of the elements of the matrix  in the region where (row1, col1) is left top corner and (row2, col2) is the right bottom corner so you can safely assume row1 <= row2 and col1 <= col2.
• void Update(int row, int col, int val): Put the value val at matrix[row][val]

Example:

Given matrix = [
  [1, 2, 3, 4],
  [5, 6, 7, 8],
  [9, 10, 11, 12],
  [13, 14, 15, 16]
]

SumRegion(1, 1, 2, 2) -> 34 (6 + 7 + 10 + 11)
update(2, 2, 5)
sumRegion(1, 1, 2, 2) -> 28 (6 + 7 + 10 + 5)

Approach: We can have the same approach which we took in our previous problem but then updates will be very expensive(O(m * n)). We can use Binary Indexed Tree here to solve our problem which are very efficient to solve these kind of problems. Obviously we need to make changes in our existing implementation of  BIT given we need to support 2D Matrix instead of 1D array but otherwise the implementation is more or less same.

To calculate the SumRegion, we will have the same formula:

SumRegion(r1, c1, r2, c2) = CumulativeSum(r2, c2) - CumulativeSum(r2, c1 - 1) - CumulativeSum(r1 - 1, c2) + CumulativeSum(r1 - 1, c1 - 1)

Rest of the things can be understood by just looking at the code. It's a mix of previous range sum query problem and binary indexed tree.

Implementation in C#:

public class NumMatrix 

{

    public NumMatrix(int[][] matrix) 

    {

        this.originalMatrix = matrix;    

        this.BuildBinaryIndexedTree();

    }

    

    public void Update(int row, int col, int val) 

    {

        int diff = val - this.originalMatrix[row][col];

        this.originalMatrix[row][col] = val;

        ++row;

        ++col;

        this.AddValueToBinaryIndexedTree(diff, row, col);

    }

    

    public int SumRegion(int row1, int col1, int row2, int col2) 

    {

        return this.GetCumulativeSum(row2, col2) - this.GetCumulativeSum(row2, col1 - 1) - this.GetCumulativeSum(row1 - 1, col2) + this.GetCumulativeSum(row1 - 1, col1 - 1);

    }

    

    private int GetCumulativeSum(int row, int col)

    {

        ++row;

        ++col;

        int sum = 0;

        for (int i = row; i > 0; i = this.GetParentIndex(i))

        {

            for (int j = col; j > 0; j = this.GetParentIndex(j))

            {

                sum += this.binaryIndexedTreeMatrix[i, j];

            }

        }  

        return sum;

    }

    

    private void BuildBinaryIndexedTree()

    {

        if (this.originalMatrix?.Length == 0)

        {

            return;

        }

        this.binaryIndexedTreeMatrix = new int[this.originalMatrix.Length + 1, this.originalMatrix[0].Length + 1];

        for (int i = 1; i <= this.originalMatrix.Length; ++i)

        {

            for (int j = 1; j <= this.originalMatrix[0].Length; ++j)

            {

                this.AddValueToBinaryIndexedTree(this.originalMatrix[i - 1][j - 1], i, j);

            }

        }

    }

    

    private void AddValueToBinaryIndexedTree(int value, int row, int col)

    {

        for (int i = row; i <= this.originalMatrix.Length; i = this.GetNextIndex(i))

        {

            for (int j = col; j <= this.originalMatrix[0].Length; j = this.GetNextIndex(j))

            {

                this.binaryIndexedTreeMatrix[i, j] += value;

            }

        }

    }

    

    private int GetParentIndex(int index)

    {

        return index - (index & -index);

    }

    private int GetNextIndex(int index)

    {

        return index + (index & -index);

    }

    

     private int[,] binaryIndexedTreeMatrix;

     private int[][] originalMatrix;

}

Complexity: Build Tree: (m * n * logm * logn), Update: O(logm * log n), SumRegion: O(logm * logn)