Finding sum of sub-matrix millions of times - PrismoSkills
Problem: Given a two-dimensional array of integers, how to optimize finding the sum of its submatrix?The submatrix is specified by two points (x1,y1) and (x2,y2).
And the submatrix sum is required to be found millions of times for many sub-matrices of this matrix.
Solution: Simplest solution to find submatrix sum is to just run two loops - from x1 to x2 and from y1 to y2.
However, since the submatrix sum can be demanded millions of times, then there must be some way to optimize this.
A good idea is to calculate the submatrix sum at every point in the original matrix and save it in a separate matrix such that sum[i][j] gives the sum of submatrix from (0,0) to (i,j).
Then the submatrix sum between any two points (x1,y1) and (x2,y2) is simply given by the following formula:
sum[x2][y2] + sum[x1][y1] - sum[x1][y2] - sum[x2][y1]
Read full article from Finding sum of sub-matrix millions of times - PrismoSkills
