Difference Arrays 2D

De ce contează?

Un cartograf colorează pe hartă mai multe regiuni dreptunghiulare, fiecare adăugând un strat de intensitate. În loc să umple fiecare celulă, notează doar colțurile fiecărui dreptunghi. La final, o singură trecere combină totul. E difference array, dar în 2D.

De la 1D la 2D

La difference array 1D adăugai x pe un interval marcând două capete. În 2D, adaugi x pe un dreptunghi marcând patru colțuri, apoi reconstruiești cu sume parțiale 2D. E tehnica pentru multe actualizări dreptunghiulare, cu răspunsul cerut la final.

Cele patru colțuri (includere-excludere)

Pentru a adăuga x pe dreptunghiul (r1,c1)..(r2,c2):

d[r1][c1]     += x;     // incepe efectul
d[r1][c2+1]   -= x;     // opreste pe orizontala
d[r2+1][c1]   -= x;     // opreste pe verticala
d[r2+1][c2+1] += x;     // coltul scazut de doua ori, readaugat

Observația-cheie

Cele patru marcaje sunt aceeași idee ca la sumele parțiale 2D, dar inversă: acolo scădeai colțul comun, aici îl readaugi. La reconstrucție, efectul lui x se propagă exact pe dreptunghi.

Reconstrucția: sume parțiale 2D

După toate actualizările, fiecare celulă devine suma cumulată 2D a vectorului de diferențe:

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

Implementare C++

#include <iostream>
using namespace std;

int main() {
    int m, n, q;
    cin >> m >> n >> q;
    long long d[1002][1002] = {0};      // +2 pentru r2+1, c2+1

    while (q--) {
        int r1, c1, r2, c2, x;
        cin >> r1 >> c1 >> r2 >> c2 >> x;
        d[r1][c1]     += x;
        d[r1][c2 + 1] -= x;
        d[r2 + 1][c1] -= x;
        d[r2 + 1][c2 + 1] += x;
    }

    // sume partiale 2D -> matricea finala
    for (int i = 1; i <= m; i++) {
        for (int j = 1; j <= n; j++) {
            d[i][j] += d[i-1][j] + d[i][j-1] - d[i-1][j-1];
            cout << d[i][j] << " ";
        }
        cout << "\n";
    }
    return 0;
}

Observația-cheie

Aloci d cu două poziții în plus pe fiecare dimensiune, fiindcă marchezi la r2+1 și c2+1. Dacă r2 = m, accesezi d[m+1] — fără marginea suplimentară, ieși din matrice.

Complexitate

Etapă	Timp	Spațiu
q actualizări	O(q)	O(m·n)
reconstrucție	O(m·n)	—
total	O(m·n + q)	O(m·n)

Naiv, fiecare actualizare ar costa O(suprafața dreptunghiului) → mult mai lent.

Greșeli frecvente

Capcane reale la difference array 2D:

Uiți colțul +x de readăugare: fără d[r2+1][c2+1] += x, zona din colț e scăzută de două ori → valori greșite.
Margini insuficiente: nu aloci +2 pe dimensiuni și accesezi în afara matricei la r2+1/c2+1.
Semne greșite la cele 4 colțuri: ordinea + − − +. O eroare de semn corupe tot dreptunghiul.
Overflow: multe actualizări cumulate depășesc int; long long.

De reținut

Difference array 2D: 4 colțuri (+ − − +) per actualizare pe dreptunghi, în O(1).
Reconstrucție prin sume parțiale 2D; alocă +2 pe fiecare dimensiune pentru r2+1/c2+1.
O(m·n + q) total; long long pentru overflow.