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

constrains:

you can't iterate matrix more once.

if name matrix there 2 of matrices available, 1 'read-only' , other 'read/write'. use 'read/write' matrix construct summed-area table.

for example code here:

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

iterares 2 times: 1) summing columns 2) summing rows

useful picture summed area tables wikipedia:

during construction, have a, b , c (for edges, zero), , want compute d. area spanned rectangle 1x1 in case, know sum of rectangle x x number original matrix @ position of d, d = c + b - + x. a subtracted because areas belonging c , b both contain area of a.

simply iterating on matrix , filling every cell using formula iterates on matrix once, , done in-place (replacing original matrix sat) if matrix not read-only.