Sume parțiale în matrice — suma oricărui dreptunghi în O(1)

De ce contează?

Vrei să afli câți locuitori sunt într-un dreptunghi de pe hartă. Dacă ai deja, pentru fiecare punct, totalul din colțul stânga-sus până la el, nu mai numeri nimic: scazi și aduni patru colțuri și ai răspunsul instant. Asta sunt sumele parțiale 2D.

Problema

Ai o matrice a și multe întrebări de forma „care e suma elementelor din submatricea de la (r1, c1) la (r2, c2)?". Naiv, fiecare răspuns costă O(suprafață). Cu sume parțiale, după o pregătire O(linii×coloane), fiecare răspuns devine O(1).

Construirea matricei de sume parțiale

Definim S[i][j] = suma dreptunghiului de la (1,1) la (i,j). Lucrăm indexat de la 1, cu rândul și coloana 0 pline cu zero (santinele), ca să evităm cazuri speciale.

Formula de construire:

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

Observația-cheie

S[i-1][j] (banda de sus) și S[i][j-1] (banda din stânga) se suprapun pe colțul stânga-sus, numărat de două ori. De aceea scazi o dată S[i-1][j-1] — incluziune-excluziune.

Interogarea unei submatrice

Suma dreptunghiului (r1,c1)–(r2,c2) se obține din patru valori ale lui S:

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 readaugi colțul scăzut de două ori. Aceeași logică ca la construire, în sens invers.

Exemplu concret

Matrice 3×3:

a = 1 2 3
    4 5 6
    7 8 9

Suma submatricei de la (2,2) la (3,3) (adică 5 6 / 8 9) e 5+6+8+9 = 28. Cu formula, după ce construiești S, obții direct 28 din patru valori.

Implementare C++

#include <iostream>
using namespace std;

int main() {
    int n = 3, m = 3;
    long long a[4][4] = {
        {0,0,0,0},
        {0,1,2,3},
        {0,4,5,6},
        {0,7,8,9}
    };
    long long S[4][4] = {0};   // rand si coloana 0 raman zero (santinele)

    // construire
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            S[i][j] = a[i][j] + S[i-1][j] + S[i][j-1] - S[i-1][j-1];
        }
    }

    // interogare: submatricea (2,2)-(3,3)
    int r1 = 2, c1 = 2, r2 = 3, c2 = 3;
    long long suma = S[r2][c2] - S[r1-1][c2] - S[r2][c1-1] + S[r1-1][c1-1];
    cout << suma << "\n";   // 28
    return 0;
}

Complexitate

Etapă	Timp	Spațiu
construire S	O(n·m)	O(n·m)
o interogare	O(1)	O(1)
q interogări naiv	O(q·n·m)	O(1)
q interogări cu S	O(n·m + q)	O(n·m)

Vizualizare

Urmărește cum se construiește matricea de sume parțiale și cum cele patru colțuri dau răspunsul:

Indiciu

Folosește ← și → pentru pași. Observă cele patru celule colorate care intră în formula de interogare.

Greșeli frecvente

Capcane la sume parțiale 2D:

Indexare de la 0 fără santinele: termenii S[i-1] și S[j-1] ies din matrice. Lucrează de la 1, cu rândul/coloana 0 pe zero.
Uiți - S[r1-1][c1-1] la interogare: scazi de două ori colțul comun și obții rezultat greșit.
Confuzi indicii interogării: r1,c1 e colțul stânga-sus (inclusiv), r2,c2 cel dreapta-jos (inclusiv). Scăderile folosesc r1-1 și c1-1.
Overflow: sumele de submatrice mari depășesc int. Folosește long long.

Recapitulare

S[i][j] = suma dreptunghiului de la (1,1) la (i,j); se construiește în O(n·m) cu incluziune-excluziune.
Orice sumă de submatrice se obține din 4 valori ale lui S, în O(1).
Folosește santinele (rând/coloană 0 pe zero) și long long pentru a evita erorile de indici și overflow.