Vectorul și matricea de diferențe

Intuiția

Ai un vector de zerouri și primești multe cereri de forma „adună v la toate elementele dintre poziția st și dr". Ideea naivă atinge fiecare element din interval — scump când intervalele sunt lungi.

Trucul: în loc să actualizezi tot intervalul, marchezi doar capetele schimbării. Reții „de la st valoarea crește cu v" și „după dr efectul dispare". La final, o singură trecere de sume parțiale propagă fiecare marcaj peste tot intervalul lui și reconstruiește vectorul real.

Vezi cum funcționează

Algoritmul pas cu pas

Pornim de la un vector de 5 zerouri (pozițiile 0..4) și două cereri:

• adună 3 pe [1, 3] → d[1] += 3, d[4] -= 3
• adună 2 pe [2, 4] → d[2] += 2, d[5] -= 2

Dimensionăm d cu o poziție în plus (0..5) ca să avem loc pentru d[dr+1] când dr = 4. După ambele actualizări, vectorul de diferențe arată așa:

Acum trecem o singură dată și acumulăm: pref[i] = pref[i-1] + d[i]. Citim doar pozițiile 0..4 (cele 5 elemente reale):

• poziția 0: 0
• poziția 1: 0 + 3 = 3
• poziția 2: 3 + 2 = 5
• poziția 3: 5 + 0 = 5
• poziția 4: 5 + (-3) = 2

Extinderea la 2D. La o matrice, „intervalul" devine un dreptunghi cu colțul stânga-sus (r1, c1) și dreapta-jos (r2, c2). Aceeași idee, dar acum un capăt se transformă în patru colțuri ale unei matrice de diferențe d:

• d[r1][c1] += v — pornește efectul din colțul stânga-sus
• d[r1][c2+1] -= v — oprește-l pe coloana de după dreptunghi
• d[r2+1][c1] -= v — oprește-l pe linia de după dreptunghi
• d[r2+1][c2+1] += v — repune ce a fost scăzut de două ori în colțul comun

Trace 2D pe o grilă 3×3. Pornim de la o matrice de zerouri (linii și coloane 0..2) și o singură cerere: adună 5 pe dreptunghiul (1,1)-(2,2) (pătratul din dreapta-jos). Marcăm cele patru colțuri într-o matrice d de 4×4 (avem nevoie de poziția 3 pentru r2+1 și c2+1):

• d[1][1] += 5
• d[1][3] -= 5 (linia r1, coloana c2+1)
• d[3][1] -= 5 (linia r2+1, coloana c1)
• d[3][3] += 5 (colțul comun)

Matricea de diferențe d arată acum așa (liniile 0..3):

Acum aplicăm sume parțiale 2D și citim doar regiunea reală 0..2. Pentru fiecare celulă: d[i][j] += sus + stanga - colt, unde sus = d[i-1][j], stanga = d[i][j-1], colt = d[i-1][j-1]. Pas cu pas în pătratul 0..2:

• (1,1) = 5 + 0 + 0 - 0 = 5
• (1,2) = 0 + 0 + 5 - 0 = 5 (preia stanga de la (1,1))
• (2,1) = 0 + 5 + 0 - 0 = 5 (preia sus de la (1,1))
• (2,2) = 0 + 5 + 5 - 5 = 5 (corecția colt scade suprapunerea)

Matricea reală reconstruită (toate celelalte celule rămân 0):

Implementare C++

Cazul 1D complet, pe exemplul de mai sus (rezultat asteptat: 0 3 5 5 2):

#include <iostream>
using namespace std;

int main() {
    int n = 5;
    int d[6] = {0};            // n+1 pozitii: loc pentru d[dr+1]

    // adauga 3 pe [1, 3]
    d[1] += 3;
    d[3 + 1] -= 3;

    // adauga 2 pe [2, 4]
    d[2] += 2;
    d[4 + 1] -= 2;

    // sume partiale: reconstruieste vectorul real
    int a[5];
    a[0] = d[0];
    for (int i = 1; i < n; i++)
        a[i] = a[i - 1] + d[i];

    for (int i = 0; i < n; i++)
        cout << a[i] << " ";   // 0 3 5 5 2
    return 0;
}

Cazul 2D complet, pe exemplul de mai sus (grila 3x3, +5 pe (1,1)-(2,2)):

#include <iostream>
using namespace std;

int main() {
    int L = 3, C = 3;
    int d[4][4] = {0};         // (L+1) x (C+1): loc pentru r2+1 si c2+1

    // adauga 5 pe dreptunghiul (1,1) - (2,2): cele patru colturi
    int r1 = 1, c1 = 1, r2 = 2, c2 = 2, v = 5;
    d[r1][c1]         += v;
    d[r1][c2 + 1]     -= v;
    d[r2 + 1][c1]     -= v;
    d[r2 + 1][c2 + 1] += v;

    // sume partiale 2D, in-place, pe regiunea reala L x C:
    for (int i = 0; i < L; i++)
        for (int j = 0; j < C; j++) {
            if (i > 0)            d[i][j] += d[i - 1][j];       // sus
            if (j > 0)            d[i][j] += d[i][j - 1];       // stanga
            if (i > 0 && j > 0)   d[i][j] -= d[i - 1][j - 1];   // colt
        }

    for (int i = 0; i < L; i++) {
        for (int j = 0; j < C; j++)
            cout << d[i][j] << " ";
        cout << "\n";
    }
    // 0 0 0
    // 0 5 5
    // 0 5 5
    return 0;
}

Complexitate

Cu q actualizări costul total e O(q + n) în 1D și O(q + L·C) în 2D — față de O(q·n) la abordarea naivă. Câștigul e uriaș când ai multe cereri pe intervale lungi.