Sume prefix 2D: suma unui dreptunghi în C++

Sumele prefix bidimensionale permit calcularea sumei unui dreptunghi dintr-o matrice în timp constant, după o precalculare. Sunt utile când matricea rămâne neschimbată și primești multe întrebări despre regiuni diferite.

O sumă prefix nu este o sumă pentru orice regiune: fiecare celulă p[i][j] descrie exact dreptunghiul dintre colțul (1,1) și colțul (i,j). Această convenție face posibilă combinarea a patru valori pentru o întrebare.

Cum funcționează

Construim p[i][j] adunând elementul curent, dreptunghiul de deasupra și dreptunghiul din stânga. Intersecția lor a fost adunată de două ori, deci o scădem o dată: p[i][j]=a[i][j]+p[i-1][j]+p[i][j-1]-p[i-1][j-1]. Linia zero și coloana zero conțin numai zerouri; ele sunt o bordură de calcul, nu fac parte din date.

Pentru colțurile inclusive (x1,y1) și (x2,y2), pornim de la p[x2][y2]. Eliminăm liniile de deasupra prin p[x1-1][y2] și coloanele din stânga prin p[x2][y1-1]. Zona din stânga sus a fost eliminată de două ori, așa că o adăugăm înapoi prin p[x1-1][y1-1]. Semnele formulei provin din suprapuneri, nu dintr-o regulă de memorat fără desen.

Programul citește n, m, q, matricea și q dreptunghiuri valide. Avem 1 <= n,m <= 100, cel mult 1000 de întrebări și elemente cu modulul cel mult un milion. Capacitatea clasică 101 include bordura, iar dimensiunile logice sunt n și m. Varianta vector alocă exact bordura și celulele utilizate. Folosim long long deoarece suma multor valori poate depăși un int.

Exemplu urmărit pas cu pas

În matricea cu liniile „1 2 3” și „4 5 6”, p[2][3] este 21. Dreptunghiul liniilor 1..2 și coloanelor 2..3 are suma 2+3+5+6=16. Formula produce 21-0-5+0=16.

Pentru o singură celulă, aceleași scăderi elimină toate celelalte elemente. Pentru întreaga matrice, cei trei termeni de bordură sunt zero. Aceste două cazuri sunt teste utile pentru erorile de indexare și funcționează inclusiv atunci când datele conțin numere negative.

Implementare C++17

Varianta cu tablou clasic:

#include <iostream>
int main() {
    int n, m, q;
    std::cin >> n >> m >> q;
    long long p[101][101] = {};
    for (int i = 1; i <= n; ++i)
        for (int j = 1; j <= m; ++j) {
            long long x;
            std::cin >> x;
            p[i][j] = x + p[i - 1][j] + p[i][j - 1] - p[i - 1][j - 1];
        }
    while (q--) {
        int x1, y1, x2, y2;
        std::cin >> x1 >> y1 >> x2 >> y2;
        std::cout << p[x2][y2] - p[x1 - 1][y2] - p[x2][y1 - 1] + p[x1 - 1][y1 - 1]
                  << '\n';
    }
}

Varianta echivalentă cu std::vector folosește aceleași limite și aceiași indici:

#include <iostream>
#include <vector>
int main() {
    int n, m, q;
    std::cin >> n >> m >> q;
    std::vector<std::vector<long long>> p(n + 1, std::vector<long long>(m + 1, 0));
    for (int i = 1; i <= n; ++i)
        for (int j = 1; j <= m; ++j) {
            long long x;
            std::cin >> x;
            p[i][j] = x + p[i - 1][j] + p[i][j - 1] - p[i - 1][j - 1];
        }
    while (q--) {
        int x1, y1, x2, y2;
        std::cin >> x1 >> y1 >> x2 >> y2;
        std::cout << p[x2][y2] - p[x1 - 1][y2] - p[x2][y1 - 1] + p[x1 - 1][y1 - 1]
                  << '\n';
    }
}

De ce funcționează și cât costă

Prin inducție pe ordinea parcurgerii, fiecare prefix conține fiecare celulă a dreptunghiului său exact o dată. Formula întrebării aplică același principiu de includere și excludere pentru a păstra exclusiv regiunea cerută.

Precalcularea costă O(nm), fiecare întrebare O(1), iar totalul O(nm+q). Memoria este O(nm). Dacă modifici ulterior un element, prefixele afectate nu se actualizează singure; algoritmul de aici este pentru date statice.

Greșeli frecvente

Nu inversa coordonatele linie-coloană și nu uita corecția intersecției. Inițializează integral bordura cu zero. Verifică limitele inclusive înainte de a scădea unu din coordonate.

Exersează

Calculează suma coloanei a doua din matricea exemplului folosind patru prefixe.

Rezolvare explicată: p[2][2]-p[0][2]-p[2][1]+p[0][1]=12-0-5+0=7, adică 2+5.

Continuă să înveți

Matrice, parcurgeri și complexitate.

Întrebări frecvente

De ce adăugăm intersecția în formula răspunsului?

Eliminarea zonei de deasupra și a celei din stânga scade intersecția lor de două ori. Adăugarea ei o readuce la contribuția zero necesară.

Funcționează și cu numere negative?

Da. Formula folosește doar adunări și scăderi, fără o presupunere de pozitivitate. Trebuie doar ca rezultatele intermediare să încapă în tipul ales.

Ce rol au linia zero și coloana zero?

Ele reprezintă prefixe vide. Permit aceeași formulă și când dreptunghiul atinge prima linie sau prima coloană.

Pot modifica matricea după precalculare?

O modificare invalidează mai multe prefixe. Pentru actualizări și întrebări intercalate sunt necesare alte structuri sau reconstruirea prefixelor.

Când merită precalcularea?

Când ai multe dreptunghiuri de interogat. Pentru o singură întrebare poți însuma direct regiunea, evitând memoria suplimentară.