Vectorul de diferențe: actualizări pe intervale

Vectorul de diferențe permite adăugarea unei valori pe un interval prin doar două modificări. După toate actualizările, o singură parcurgere reconstruiește valorile finale. Metoda este potrivită când răspunsul este cerut la sfârșit, nu după fiecare operație.

Pornim de la un tablou de zerouri. Fiecare operație (l,r,x) adaugă x tuturor pozițiilor de la l la r inclusiv. O implementare directă ar putea vizita aproape tot tabloul la fiecare operație; diferențele înregistrează doar începutul și sfârșitul efectului.

Cum funcționează

Dacă d[i]=a[i]-a[i-1], cu a[0]=0, atunci a[i] este suma d[1]+...+d[i]. Adăugarea lui x pe intervalul [l,r] schimbă diferența de la l cu +x. La r+1 efectul trebuie să se oprească, deci diferența de acolo se schimbă cu -x. În interiorul intervalului, două valori vecine cresc la fel, iar diferența lor nu se modifică.

După ce înregistrăm toate operațiile, acumulăm current de la stânga la dreapta. La fiecare poziție afișăm suma diferențelor întâlnite. Operațiile se pot suprapune, deoarece contribuțiile lor se adună. Valorile negative funcționează la fel: o actualizare cu -3 înseamnă scăderea lui 3 din interval.

Programul presupune 1 <= n <= 100000, 0 <= q <= 100000, intervale valide și valori x cu modulul cel mult un miliard. Capacitatea 100002 include poziția n+1 unde oprim o actualizare care ajunge la final. Dimensiunea logică afișată rămâne n. Vectorul echivalent alocă n+2 celule. Dacă tabloul inițial nu este zero, construim mai întâi diferențele sale sau adăugăm acumularea finală peste valorile inițiale.

Exemplu urmărit pas cu pas

Pentru n=5, adăugăm 3 pe [2,4] și apoi -1 pe [3,5]. Prima operație produce d[2]+=3 și d[5]-=3. A doua produce d[3]-=1 și d[6]+=1.

Pe pozițiile 1..5 diferențele sunt 0,3,-1,0,-3. Sumele lor prefix sunt 0,3,2,2,-1, exact tabloul final. Poziția 6 nu se afișează, dar păstrarea ei elimină un caz special din actualizare și face formula uniformă.

Implementare C++17

Varianta cu tablou clasic:

#include <iostream>
int main() {
    int n, q;
    std::cin >> n >> q;
    long long d[100002] = {};
    while (q--) {
        int l, r;
        long long x;
        std::cin >> l >> r >> x;
        d[l] += x;
        d[r + 1] -= x;
    }
    long long current = 0;
    for (int i = 1; i <= n; ++i) {
        current += d[i];
        std::cout << current << (i == n ? '\n' : ' ');
    }
}

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

#include <iostream>
#include <vector>
int main() {
    int n, q;
    std::cin >> n >> q;
    std::vector<long long> d(n + 2, 0);
    while (q--) {
        int l, r;
        long long x;
        std::cin >> l >> r >> x;
        d[l] += x;
        d[r + 1] -= x;
    }
    long long current = 0;
    for (int i = 1; i <= n; ++i) {
        current += d[i];
        std::cout << current << (i == n ? '\n' : ' ');
    }
}

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

Pentru o operație, contribuția la suma prefix este zero înainte de l, x între l și r și zero după r. Prin adunarea contribuțiilor tuturor operațiilor, fiecare poziție primește exact actualizările care o conțin.

Înregistrarea unei operații costă O(1), reconstrucția O(n), iar totalul O(n+q). Memoria este O(n). Dacă trebuie să răspunzi online după fiecare actualizare, reconstruirea repetată poate deveni prea lentă și este necesară altă structură.

Greșeli frecvente

Nu scădea la r, deoarece ai elimina contribuția ultimului element inclus. Nu afișa diferențele în locul sumelor lor prefix. Nu aloca doar n+1 celule când accesezi n+1 cu indexare de la unu.

Exersează

Pentru n=3, aplică +4 pe [1,3] și -2 pe [2,2]. Scrie diferențele și rezultatul.

Rezolvare explicată: Diferențele pe 1..4 sunt 4,-2,2,-4. Sumele prefix afișate sunt 4,2,4. Ultima diferență închide efectul, fără să reprezinte un element al rezultatului.

Continuă să înveți

Sume prefix 2D, secvențe și complexitate.

Întrebări frecvente

De ce scădem la r+1?

Intervalul include poziția r. Contribuția trebuie anulată abia începând cu următoarea poziție, astfel încât suma prefix să păstreze actualizarea până la r inclusiv.

Pot suprapune actualizările?

Da. Adunarea este liniară: fiecare operație adaugă independent contribuția sa, iar reconstrucția însumează toate contribuțiile active.

Funcționează pentru scăderi?

Da, folosește o valoare x negativă. Nu este nevoie să schimbi formula sau sensul parcurgerii.

Care este legătura cu sumele prefix?

Diferențele desfac variația dintre elemente vecine, iar sumele prefix reconstruiesc valorile. Cele două transformări sunt inverse, cu aceeași convenție pentru elementul zero.

Pot cere suma unui interval între două actualizări?

Implementarea prezentată nu oferă această operație eficient online. Pentru cerințe intercalate trebuie analizate alte structuri, precum arborii Fenwick sau arborii de intervale.