Sume parțiale 2D

Am învățat sumele parțiale pe vectori - calculam suma pe orice interval [st, dr] în O(1). Acum extindem ideea la matrici: calculăm suma pe orice submatrice (r1, c1) -> (r2, c2) în O(1).

Problema

Avem o matrice n x m și q întrebări de forma: “care este suma elementelor din submatricea cu colțul stânga-sus (r1, c1) și colțul dreapta-jos (r2, c2)?”

Matrice 4 x 4:
1 2 3 4
5 6 7 8
9 1 2 3
4 5 6 7

Întrebare: suma pe (2,2) -> (3,4) = 6+7+8+1+2+3 = 27

Cu parcurgere: O(nm) per întrebare. Cu q întrebări: O(qn*m).

Cu sume parțiale 2D: O(1) per întrebare, după O(n*m) precalculare.

Vectorul de sume parțiale 2D

Definim sp[i][j] = suma tuturor elementelor din submatricea (1,1) -> (i,j).

a:              sp:
1 2 3 4         1  3  6  10
5 6 7 8         6  14 24 36
9 1 2 3         15 24 36 51
4 5 6 7         19 33 51 73

De exemplu: sp[2][3] = 1+2+3+5+6+7 = 24 (suma primelor 2 linii, primele 3 coloane).

Construirea

Formula:

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

De ce scădem sp[i-1][j-1]? Pentru că a fost adunată de două ori (o dată prin sp[i-1][j], o dată prin sp[i][j-1]).

Vizual - principiul includere-excludere:

sp[i-1][j-1]  |  sp[i-1][j]
─────────────-+──────────
sp[i][j-1]    |  a[i][j]
              ↗
sp[i][j] = a[i][j] + sus + stânga - colț

sp[0][0] = 0;
for (int i = 0; i <= n; i++) sp[i][0] = 0;
for (int j = 0; j <= m; j++) sp[0][j] = 0;

for (int i = 1; i <= n; i++)
    for (int j = 1; j <= m; j++)
        sp[i][j] = a[i][j] + sp[i - 1][j] + sp[i][j - 1] - sp[i - 1][j - 1];

Formula pentru suma pe submatrice

Suma pe submatricea (r1, c1) -> (r2, c2):

suma = sp[r2][c2] - sp[r1-1][c2] - sp[r2][c1-1] + sp[r1-1][c1-1]

Vizual:

+──────────+──────+
|  sp[r1-1][c1-1]  |  sp[r1-1][c2]
+──────────+──────+
|  sp[r2][c1-1]    | sp[r2][c2]
+──────────+──────+

Scădem banda de sus, scădem banda din stânga, adăugăm colțul (scăzut de 2 ori).

Codul complet

#include <fstream>
using namespace std;
ifstream fin("date.in");
ofstream fout("date.out");

int a[1001][1001];
long long sp[1001][1001];
int n, m, q;

int main()
{
    fin >> n >> m >> q;

    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= m; j++)
            fin >> a[i][j];

    // Construim sume parțiale 2D
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= m; j++)
            sp[i][j] = a[i][j] + sp[i - 1][j] + sp[i][j - 1] - sp[i - 1][j - 1];

    // Răspundem la întrebări
    for (int i = 1; i <= q; i++) {
        int r1, c1, r2, c2;
        fin >> r1 >> c1 >> r2 >> c2;
        long long suma = sp[r2][c2] - sp[r1 - 1][c2] - sp[r2][c1 - 1] + sp[r1 - 1][c1 - 1];
        fout << suma << "\n";
    }

    return 0;
}

date.in:

4 4 3
1 2 3 4
5 6 7 8
9 1 2 3
4 5 6 7
2 2 3 4
1 1 4 4
3 3 4 4

date.out:

27
73
18

Verificare

• (2,2) -> (3,4): 6+7+8+1+2+3 = 27
• (1,1) -> (4,4): toată matricea = 73
• (3,3) -> (4,4): 2+3+6+7 = 18

Exemplu pas cu pas

Suma pe (2,2) -> (3,4):

sp[3][4] = 51      (tot de la (1,1) la (3,4))
sp[1][4] = 10      (banda de sus)
sp[3][1] = 15      (banda din stânga)
sp[1][1] = 1       (colțul - scăzut de 2 ori)

suma = 51 - 10 - 15 + 1 = 27 ✓

Comparație

Greșeli frecvente

1. Uitarea inițializării liniei/coloanei 0

// sp[0][j] și sp[i][0] trebuie să fie 0
// Dacă declarăm global, sunt deja 0

2. Formula greșită - semnele inversate

// GREȘIT:
sp[r2][c2] + sp[r1-1][c2] - sp[r2][c1-1] - sp[r1-1][c1-1]

// CORECT:
sp[r2][c2] - sp[r1-1][c2] - sp[r2][c1-1] + sp[r1-1][c1-1]

Scădem două, adunăm unul. Includere-excludere.

3. Depășire la int

Dacă elementele sunt mari și matricea e mare, suma poate depăși int. Folosește long long pentru sp.

Ce să reții

• sp[i][j] = suma submatricei (1,1) -> (i,j).
• Construire: sp[i][j] = a[i][j] + sp[i-1][j] + sp[i][j-1] - sp[i-1][j-1].
• Interogare: sp[r2][c2] - sp[r1-1][c2] - sp[r2][c1-1] + sp[r1-1][c1-1].
• Includere-excludere: scădem 2 zone, adăugăm colțul.
• Precalculare O(n*m), interogare O(1).

Probleme

pbinfoCirese1→

pbinfoMaria→

pbinfoGradina→