Gibt es eine Möglichkeit, eine summierte-are-Tabelle einer Matrix mit nur einer Iteration zu erstellen?

Question

Einschränkungen:

Sie können die Matrix nicht mehr als einmal durchlaufen.

Wenn wir die Matrix A benennen, dann gibt es zwei dieser Matrizen, eine ist 'read-only' und die andere ist 'read/write'. Wir werden die "Lese/Schreib" -Matrix verwenden, um die summierte Flächentabelle zu konstruieren.

Zum Beispiel dieser Code hier:

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

Iterares 2mal: 1) das Summieren aller Spalten 2) Summieren aller Zeilen

Answer 1

brauchbares Bild für summierten Bereich Tabellen aus Wikipedia:

Während des Baus haben wir bereits hav e A, B und C (für die Kanten wären sie Null), und wollen berechnen. Der Bereich, der durch dieses Rechteck aufgespannt wird, ist in diesem Fall 1x1, daher wissen wir, dass die Summe des Rechtecks ​​X ist, wobei X die Nummer der ursprünglichen Matrix an der Position ist, also D = C + B - A + X. A wird subtrahiert, da die Bereiche C und B beide den Bereich A enthalten.

Einfach über die Matrix zu iterieren und jede Zelle mit dieser Formel zu füllen, iteriert nur einmal über die Matrix und könnte sogar direkt durchgeführt werden (Ersetzen der ursprünglichen Matrix durch ihre SAT), wenn Ihre Matrix nicht schreibgeschützt ist.