Sume parțiale în matrice

De ce contează?

Ai o hartă cu numărul de oameni din fiecare cartier și vrei populația oricărei zone dreptunghiulare, rapid și de multe ori. În loc s-o aduni de fiecare dată, precalculezi „câți sunt în tot colțul până aici" și apoi combini patru numere. Asta sunt sumele parțiale 2D.

De la 1D la 2D

Ca la vectori, ideea e să precalculezi sume cumulate. În 2D, S[i][j] = suma întregului dreptunghi din colțul (1,1) până la (i,j). Folosim indexare de la 1, cu o linie și o coloană de zerouri la margine (ca neutru pentru scăderi).

Construirea: includere și excludere

S[i][j] = a[i][j] + S[i-1][j] + S[i][j-1] - S[i-1][j-1];

Aduni dreptunghiul de deasupra și pe cel din stânga, dar zona comună (colțul stânga-sus) a fost numărată de două ori → o scazi o dată.

Observația-cheie

Termenul − S[i-1][j-1] e inima formulei: S[i-1][j] și S[i][j-1] se suprapun pe tot dreptunghiul (1,1)..(i-1,j-1). Includere-excludere îl corectează scăzându-l o singură dată.

Suma unui dreptunghi din 4 valori

Suma dreptunghiului cu colțuri (r1,c1) (stânga-sus) și (r2,c2) (dreapta-jos):

suma = S[r2][c2] - S[r1-1][c2] - S[r2][c1-1] + S[r1-1][c1-1];

Scazi banda de deasupra și banda din stânga, apoi adaugi înapoi colțul scăzut de două ori.

Implementare C++

#include <iostream>
using namespace std;

int main() {
    int m, n;
    cin >> m >> n;
    long long a[101][101], S[101][101] = {0};
    for (int i = 1; i <= m; i++)
        for (int j = 1; j <= n; j++) {
            cin >> a[i][j];
            S[i][j] = a[i][j] + S[i-1][j] + S[i][j-1] - S[i-1][j-1];
        }

    int q;
    cin >> q;
    while (q--) {
        int r1, c1, r2, c2;
        cin >> r1 >> c1 >> r2 >> c2;
        long long suma = S[r2][c2] - S[r1-1][c2] - S[r2][c1-1] + S[r1-1][c1-1];
        cout << suma << "\n";       // suma dreptunghiului in O(1)
    }
    return 0;
}

Observația-cheie

Indexarea de la 1 cu linia/coloana 0 pline de zerouri face formulele să meargă și pentru dreptunghiuri lipite de margine (r1 = 1 sau c1 = 1), fără cazuri speciale. La fel ca la sumele parțiale 1D, dar cu un colț în plus de corectat.

Complexitate

Etapă	Timp	Spațiu
precalculare	O(m·n)	O(m·n)
o interogare	O(1)	—
q interogări (naiv)	O(q·m·n)	—

Greșeli frecvente

Capcane reale la sumele parțiale 2D:

Uiți − S[i-1][j-1] la construire: numeri colțul de două ori → toate sumele greșite.
Semne greșite la interogare: formula are − − +; o eroare de semn dă rezultate aberante. Verifică pe un dreptunghi mic.
Indexare de la 0 fără margine: accesezi S[-1][...]. Folosește indexare de la 1 cu rândul/coloana 0 pe zero.
Overflow: sumele de dreptunghiuri mari se sparg; long long peste tot.

Vizualizare

Urmărește cum se construiește matricea cumulată și cum suma unui dreptunghi se obține din 4 colțuri:

Indiciu

Observă cele 4 colțuri folosite la o interogare: dreptunghiul mare, minus cele două benzi, plus colțul scăzut de două ori. Includere-excludere, vizual.

De reținut

S[i][j] = suma dreptunghiului (1,1)..(i,j); construit cu includere-excludere (− S[i-1][j-1]).
Suma unui dreptunghi = S[r2][c2] − S[r1-1][c2] − S[r2][c1-1] + S[r1-1][c1-1], în O(1).
Indexare de la 1 cu margine de zerouri; long long pentru overflow.