De ce contează?
Ești pontatorul unei hale cu rafturi așezate în grilă și tot timpul cineva te întreabă „câte cutii sunt în zona asta dreptunghiulară?". Ai putea număra de fiecare dată raft cu raft — dar te-ai prins repede că e mai deștept să ții un singur tabel: pentru fiecare colț (i, j) notezi câte cutii sunt în tot dreptunghiul de la colțul din stânga-sus până aici. Cu tabelul ăsta, orice zonă ți-o cere cineva o afli din câteva scăderi, fără să mai numeri nimic.
Intuiția
O sumă-prefix 2D este un tabel S în care S[i][j] reține suma întregii
submatrice din colțul (1, 1) până la (i, j). Odată construit, suma oricărui
dreptunghi nu se mai calculează adunând celule, ci combinând patru valori deja
gata: iei marele dreptunghi până la colțul de jos-dreapta, scoți fâșia de
deasupra și fâșia din stânga, iar colțul comun (scos de două ori) îl pui la loc.
E aceeași idee de la sumele parțiale pe vector, dar pe două dimensiuni: acolo o
sumă de interval era o scădere între două prefixe; aici un dreptunghi e o
combinație între patru.