Is there a way to create a summed-are table of a matrix with just one iteration?

Question

Constrains:

You can't iterate the matrix more than once.

If we name the matrix A then there are two of those matrices available, one is 'read-only' and the other is 'read/write'. We will use the 'read/write' matrix to construct the summed-area table.

For example this code here:

http://www.geeksforgeeks.org/submatrix-sum-queries/

Iterares 2 times: 1) summing all columns 2) summing all rows

Answer 1

Useful picture for summed area tables from Wikipedia:

During construction, we already have A, B and C (for the edges, they would be zero), and want to compute D. The area spanned by that rectangle is 1x1 in this case, so we know the sum of the rectangle is X where X is the number from the original matrix at the position of D, so D = C + B - A + X. A is subtracted because the areas belonging to C and B both contain the area of A.

Simply iterating over the matrix and filling every cell using that formula iterates over the matrix only once, and could even be done in-place (replacing the original matrix by its SAT) if your matrix was not read-only.