Șmenul lui Mars 2D

Am învățat Șmenul lui Mars pe vectori: adunăm o valoare pe un interval în O(1) folosind marcaje +val și -val. Acum extindem tehnica la matrici: adunăm o valoare pe o submatrice în O(1).

Problema

Avem o matrice n x m, inițial cu zerouri. Primim q operații:

Adaugă val pe toată submatricea (r1, c1) -> (r2, c2).

La final, vrem matricea rezultată.

Ideea

La fel ca pe vectori, folosim 4 marcaje în loc să parcurgem toată submatricea:

d[r1][c1]     += val;    // pornește adunarea
d[r1][c2 + 1] -= val;    // oprește pe orizontală
d[r2 + 1][c1] -= val;    // oprește pe verticală
d[r2 + 1][c2 + 1] += val; // compensează colțul (scăzut de 2 ori)

Apoi reconstruim matricea cu sume parțiale 2D.

De ce 4 marcaje?

E includere-excludere inversă:

Operația: +3 pe (2,2) -> (3,4)

Marcaje în d:
     1    2    3    4    5
1    .    .    .    .    .
2    .   +3    .    .   -3
3    .    .    .    .    .
4    .   -3    .    .   +3

După sume parțiale 2D:
     1    2    3    4    5
1    0    0    0    0    0
2    0    3    3    3    0
3    0    3    3    3    0
4    0    0    0    0    0

Exact submatricea (2,2)-(3,4) a primit +3.

Reconstrucția cu sume parțiale

După ce am pus toate marcajele, calculăm sumele parțiale pe d - exact ca la sume parțiale 2D, dar acum construim rezultatul:

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

Codul complet

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

int d[1002][1002];
int n, m, q;

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

    for (int i = 1; i <= q; i++) {
        int r1, c1, r2, c2, val;
        fin >> r1 >> c1 >> r2 >> c2 >> val;

        d[r1][c1] += val;
        d[r1][c2 + 1] -= val;
        d[r2 + 1][c1] -= val;
        d[r2 + 1][c2 + 1] += val;
    }

    // Reconstruim cu sume parțiale 2D
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= m; j++)
            d[i][j] = d[i][j] + d[i - 1][j] + d[i][j - 1] - d[i - 1][j - 1];

    // Afișăm
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++)
            fout << d[i][j] << " ";
        fout << "\n";
    }

    return 0;
}

date.in:

4 5 3
2 2 3 4 3
1 1 4 5 1
3 3 4 4 2

date.out:

1 1 1 1 1
1 4 4 4 1
1 4 6 6 1
1 4 3 3 1

Verificare

• Operația 1: +3 pe (2,2)-(3,4)
• Operația 2: +1 pe (1,1)-(4,5)
• Operația 3: +2 pe (3,3)-(4,4)

Elementul (3,3): 3 + 1 + 2 = 6 ✓

Exemplu detaliat: o singură operație

+5 pe submatricea (2,1)-(3,3) în matrice 4x4:

Pasul 1: marcaje

d:
 0  0  0  0  0
+5  0  0 -5  0
 0  0  0  0  0
-5  0  0 +5  0
 0  0  0  0  0

Pasul 2: sume parțiale 2D

Corect - submatricea (2,1)-(3,3) a primit +5.

Când vectorul inițial nu e zero

Dacă matricea are valori inițiale a[i][j], le adăugăm la final:

for (int i = 1; i <= n; i++)
    for (int j = 1; j <= m; j++)
        fout << a[i][j] + d[i][j] << " ";

Comparație

Greșeli frecvente

1. Uitarea colțului d[r2+1][c2+1] += val

Fără acest marcaj, scăderile pe orizontală și verticală se suprapun greșit. Trebuie compensat colțul.

2. Vectorul d prea mic

Facem d[r2 + 1][c2 + 1], deci dacă n sau m sunt maxime, avem nevoie de d[n + 2][m + 2].

3. Ordinea greșită la sume parțiale

Formula de reconstrucție e identică cu cea de construire a sumelor parțiale 2D. Nu inversa semnele.

Ce să reții

• 4 marcaje per operație: +val, -val, -val, +val pe cele 4 colțuri.
• Reconstrucția: sume parțiale 2D pe matricea de diferențe.
• Complexitate: O(1) per operație, O(n*m) reconstrucție.
• Extensia naturală a Șmenului lui Mars pe vectori.
• Vectorul d trebuie să aibă n + 2 linii și m + 2 coloane.

Probleme

pbinfoLivada2→

pbinfoTeren→

pbinfoPasari→