Range Sum Query 2D

Problem: 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). Implement the NumMatrix class:

1. NumMatrix(int[][] matrix) Initializes the object with the 2D integer array matrix.
2. 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.

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 = 34)
SumRegion(0, 0, 2, 1) -> 33 (1 + 2 + 5 + 6 + 9 + 10 = 33)

Approach: One obvious approach is to save input matrix as is and in SumRegion method we can iterate through every element of the input region and return the sum. This will work but SumRegion will take O(m*n) time. We need to optimize it.

Another approach is we can use the approach of previous problem Range Sum Query (1D array). We can treat each row as separate array. The same precomputation and SumRange method can be applied on each and every row and then we can take the sum of all the rows(arrays) and return. It will take O(n) time which is way better than the brute force approach. Can we optimize it further? Let's see how:

We can precompute a cumulative region sum with respect to the origin at (0, 0). That means we can have a matrix say SumMatrix where SumMatrix[i][j] will have the sum of every element in the region with (0, 0) as left top corner and (i, j) as right bottom corner. In simple language:

SumMatrix[i][j] = Sum of all InputMatrix[x][y] where 0 <= x <= i and 0 <= y <= j

If we use pencil and paper and calculate cumulative sum in this way we will find out that:

SumMatrix[i][j] = SumMatrix[i][j-1] + SumMatrix[i-1][j] + InputMatrix[i][j] - SumMatrix[i-1][j-1]

Let's visualize it using an example. Take the example from the description:

Now let's see how we can calculate SumMatrix[1][1]:

If you see to calculate SumMatrix[1][1] we need sum of region (0,0) to (0, 1) that is SumMatrix[0][1] and region (0, 0) to (1, 0) that is SumMatrix[1][0] and current element. But If you see in this sum SumMatrix[0][0] came 2 times so we need to subtract it. That means:

SumMatrix[1][1] = SumMatrix[1][0] + SumMatrix[0][1] + InputMatrix[1][1] - SumMatrix[0][0]

If you see the above calculation, it matches with the statement I have given to calculate SumMatrix[i][j].

Now Let's see how we can calculate sum of the input region efficiently. Here is the calculated SumMatrix for the given example:

Say we want to calculate sum of the region (1, 1) to (2, 2):

Here is how we can calculate it:

Here is the sum of region (0, 0) to (2, 2) which is SumMatrix[2][2]:

But we don't want this. We actually want the following:

So looking at the picture we can say our target sum will be:

Sum of Region (0, 0) to (2, 2) - Sum of Region (0, 0) to (0, 2) - Sum of Region (0,0) to (2, 0) + Sum of Region (0, 0) to (0, 0) 

= SumMatrix[2][2] - SumMatrix[0][2] - SumMatrix[2][0] + SumMatrix[0][0]

We are adding Sum of region (0, 0) to (0, 0) as if you see we are subtracting it twice with (0, 0) to (0, 2) and (0, 0) to (2, 0). Now let's drive the formula by looking at it

Sum of region (r1, c1) to (r2, c2) = SumMatrix[r2][c2] - SumMatrix[r1-1][c2] - SumMatrix[r2][c1-1] + SumMatrix[r1-1][c1-1]

That's all. Hopefully you could understand the approach easily.

Implementation in C#:

    public class NumMatrix

    {

        public NumMatrix(int[][] matrix)

        {

            if (matrix.Length > 0 && matrix[0].Length > 0)

            {

                this.sumMatrix = new int[matrix.Length + 1, matrix[0].Length + 1];

                for (int i = 1; i < this.sumMatrix.GetLength(0); ++i)

                {

                    for (int j = 1; j < this.sumMatrix.GetLength(1); ++j)

                    {

                        this.sumMatrix[i, j] = this.sumMatrix[i, j - 1] + this.sumMatrix[i - 1, j] + matrix[i - 1][j - 1] - this.sumMatrix[i - 1, j - 1];

                    }

                }

            }

        }

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

        {

            if (this.sumMatrix == null)

            {

                return 0;

            }

            if (row1 == 0 && col1 == 0)

            {

                return this.sumMatrix[row2 + 1, col2 + 1];

            }

            

            return this.sumMatrix[row2 + 1, col2 + 1] - this.sumMatrix[row1, col2 + 1] - this.sumMatrix[row2 + 1, col1] + this.sumMatrix[row1, col1];

        }

        private int[,] sumMatrix;

    }

Complexity: O(m*n) for precomputation and O(1) for SumRegion.