Difference Arrays 1D

De ce contează?

Un controlor de bilete trebuie să adauge câte un loc ocupat pe intervale lungi de scaune, de multe ori. În loc să bifeze fiecare scaun, notează doar „de aici începe" și „aici se termină". La final trece o dată și calculează totul. Difference array face exact asta.

Problema: multe actualizări pe intervale

Ai un vector și primești multe operații „adună x la toate elementele din [st, dr]". Aplicate naiv, fiecare costă O(lungime interval) → O(q·n) total, prea lent. Vectorul de diferențe face fiecare actualizare în O(1) și reconstruiește la final.

Ideea: marchezi doar începutul și sfârșitul

Ții un vector d în care marchezi schimbările, nu valorile:

d[st] += x — de aici încolo, adaugă x.
d[dr+1] -= x — chiar după dr, anulează efectul.

La final, sumele parțiale ale lui d dau vectorul real.

Algoritm pas cu pas

Vector de 6 zerouri. Operații: „+5 pe [1,3]", apoi „+2 pe [2,4]". Marcăm în d:

d	0	5	2	0	-5	-2	0
i	0	1	2	3	4	5	6

După cele două operații: +5 la d[1], −5 la d[4]; +2 la d[2], −2 la d[5]. Doar capetele intervalelor sunt atinse.

Sumele parțiale ale lui d (de la 1): 5, 7, 7, 2, 0 → vectorul final pe pozițiile 1..5.

i	d[i]	v[i] = v[i-1] + d[i]
1	5	5
2	2	7
3	0	7
4	−5	2
5	−2	0

Implementare C++

#include <iostream>
using namespace std;

int main() {
    int n, q;
    cin >> n >> q;
    long long d[100002] = {0};      // vector de diferente, initializat 0

    while (q--) {
        int st, dr, x;
        cin >> st >> dr >> x;
        d[st] += x;                 // incepe efectul
        d[dr + 1] -= x;             // opreste efectul dupa dr
    }

    long long v = 0;
    for (int i = 1; i <= n; i++) {
        v += d[i];                  // sume partiale -> valoarea reala
        cout << v << " ";
    }
    return 0;
}

Observația-cheie

Magia stă în d[dr+1] -= x: când faci sumele parțiale, efectul lui +x se propagă de la st încolo, iar -x de la dr+1 îl anulează — deci x se aplică exact pe [st, dr]. Dimensionează d cu o poziție în plus pentru dr+1.

Difference array vs sume parțiale

Sunt operații inverse: sumele parțiale reconstruiesc valori din diferențe; difference array înregistrează schimbări pe care le „desfaci" cu sume parțiale. Una e pentru interogări pe interval, cealaltă pentru actualizări pe interval.

Complexitate

Metodă	q actualizări	reconstruire	Total
difference array	O(q)	O(n)	O(n + q)
naiv (per element)	O(q·n)	—	O(q·n)

Greșeli frecvente

Capcane reale la difference arrays:

Uiți d[dr+1] -= x: efectul lui x curge până la capătul vectorului, nu se oprește la dr.
Depășești dimensiunea la dr+1: dacă dr = n, accesezi d[n+1]. Alocă o poziție în plus.
Uiți sumele parțiale finale: rămâi cu vectorul de diferențe, nu cu valorile reale.
Overflow: multe actualizări cumulate pot depăși int; folosește long long.

Vizualizare

Urmărește cum o actualizare pe interval atinge doar două poziții, iar sumele parțiale refac vectorul:

Indiciu

Observă că o operație pe un interval lung atinge doar capetele în vectorul de diferențe. Toată „umplerea" intervalului se întâmplă abia la pasul de sume parțiale.

De reținut

Difference array: d[st] += x, d[dr+1] -= x → actualizare pe interval în O(1).
Vectorul final = sumele parțiale ale lui d (v[i] = v[i-1] + d[i]).
O(n + q) total; alocă o poziție în plus pentru dr+1 și folosește long long.