De ce contează?
Imaginează-ți o hartă de căldură a unui oraș: fiecare celulă a unui caroiaj arată câți oameni au trecut pe acolo într-o oră. Cineva te întreabă mereu același tip de lucru: „câți oameni au fost în dreptunghiul ăsta de străzi?”, apoi „dar în ăsta?”, de sute de ori. Să numeri celulele din nou la fiecare întrebare e epuizant. Dacă în schimb ai pregăti o dată un tabel deștept, ai răspunde la orice dreptunghi dintr-o singură privire — citind doar patru numere, oricât de mare ar fi zona. Exact asta fac sumele parțiale 2D.
Intuiția
Știi deja sumele parțiale pe un vector: P[i] ține suma primelor i elemente, iar
suma unui interval e o scădere. În două dimensiuni ideea e aceeași, doar că „prefixul”
e un dreptunghi: P[i][j] va ține suma tuturor celulelor din colțul stânga-sus
(1,1) până la (i,j). Odată ce ai acest tablou, suma oricărui dreptunghi se obține
combinând câteva astfel de dreptunghiuri prin includere-excludere — fără să mai atingi
celulele originale.
Două formule duc toată lecția. La construcție, fiecare celulă lipește dreptunghiul
de deasupra cu cel din stânga și scade colțul numărat de două ori:
P[i][j] = a[i][j] + P[i-1][j] + P[i][j-1] - P[i-1][j-1]. La interogare, suma unui
dreptunghi e tot includere-excludere, dar pe 4 valori deja calculate — deci O(1),
oricât de mare ar fi dreptunghiul.