[Solved]: Efficient way to calculate sum in sliding window?

Problem Detail: 

Assume you have a grid as below:

The square is the sliding window. I want to slide this window over all the possible position such that the window is contained in the grid (i.e the edges of the window should not cross the boundaries of the grid.)

For each such position I want to calculate the sum of the cells in the window. I'd like to be able to do this with different sizes of windows as well. More specifically, given some range for the possible widths and possible heights of windows, I want to calculate and store all the sums over the cells in the window, for all positions of the window, and for all possible width/height combinations.

As an example: if the possible widths are 2 and 3 and the possible heights are 4, 5 and 6, then there are 6 combinations: $2 \times 4$, $2 \times 5$, $2 \times 6$ $3 \times 4$, $3 \times 5$, $3 \times 6$ and for each such sliding window size, I want to store the sums over cells in the sliding window for all possible positions of the sliding window.

What would be an efficient way to do this?

Cheers

Asked By : fiftyeight

Answered By : Tom van der Zanden

One possible way would be to store the sum of all the submatrices of the form $((0,0),(i,j))$. You can compute each of these sums in $O(1)$ time per entry (by using the previous entries).

If you then want to know the sum of the submatrix $((x,y),(i,j))$, you can compute this in $O(1)$ from the stored sums using inclusion-exclusion. If we let $S$ denote such a sum, then

$$S((x,y),(i,j))=S((0,0),(i,j))-S((0,0),(x,j))-S((0,0),(i,y))+S((0,0),(x,y))$$

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/39529