Șmenul lui Mars (Difference Arrays)

Șmenul lui Mars (cunoscut și ca Difference Array sau vectorul de diferențe) este o tehnică prin care putem face adunări pe intervale foarte eficient.

Problema

Avem un vector cu n elemente, inițial toate 0. Primim q operații de forma:

Adaugă valoarea val la toate elementele de la poziția st la poziția dr.

La final, vrem să aflăm vectorul rezultat.

Exemplu

n = 8, initial: 0 0 0 0 0 0 0 0

Operatia 1: adauga 3 pe [2, 5]  ->  0 3 3 3 3 0 0 0
Operatia 2: adauga 2 pe [4, 7]  ->  0 3 3 5 5 2 2 0
Operatia 3: adauga 1 pe [1, 3]  ->  1 4 4 5 5 2 2 0

Abordarea naivă (lentă)

Pentru fiecare operație, parcurgem intervalul și adunăm:

for (int i = st; i <= dr; i++) {
    v[i] = v[i] + val;
}

Dacă avem q operații și fiecare interval are lungime până la n, facem q * n operații.

Pentru n = 100.000 și q = 100.000, asta înseamnă 10^10 operații - prea lent.

Ideea șmenului lui Mars

În loc să adunăm val pe fiecare poziție din interval, facem doar două marcaje:

1. d[st] = d[st] + val - marcăm începutul intervalului
2. d[dr + 1] = d[dr + 1] - val - marcăm sfârșitul (anulăm efectul după dr)

La final, parcurgem vectorul d și calculăm sumele parțiale - obținem vectorul final.

De ce funcționează?

Gândește-te că d[st] += val înseamnă “de aici încolo, adaugă val”. Iar d[dr+1] -= val înseamnă “de aici încolo, oprește adunarea”.

Când calculăm sumele parțiale peste d, fiecare poziție din [st, dr] primește exact val, iar pozițiile din afara intervalului nu sunt afectate.

Exemplu detaliat

n = 8

Operatia 1: adauga 3 pe [2, 5]
Operatia 2: adauga 2 pe [4, 7]
Operatia 3: adauga 1 pe [1, 3]

Pasul 1: marcăm operațiile în vectorul d

Vectorul d după toate operațiile:

indice:  1   2   3   4   5   6   7   8
d:       1   3   0   1   0  -3   0  -2

Pasul 2: calculăm sumele parțiale

Rezultat: 1 4 4 5 5 2 2 0

Verificare cu metoda naiva:

Dupa op 1: 0 3 3 3 3 0 0 0
Dupa op 2: 0 3 3 5 5 2 2 0
Dupa op 3: 1 4 4 5 5 2 2 0  ✓

Codul complet

#include <fstream>
using namespace std;
ifstream fin("date.in");
ofstream fout("date.out");

int d[100002]; // vectorul de diferente (cu o pozitie in plus)
int n, q;

int main()
{
    fin >> n >> q;

    // Citim operațiile și marcăm
    for (int i = 1; i <= q; i++) {
        int st, dr, val;
        fin >> st >> dr >> val;
        d[st] = d[st] + val;
        d[dr + 1] = d[dr + 1] - val;
    }

    // Calculăm sumele parțiale și afișăm
    int suma = 0;

    for (int i = 1; i <= n; i++) {
        suma = suma + d[i];
        fout << suma << " ";
    }

    return 0;
}

date.in:

8 3
2 5 3
4 7 2
1 3 1

date.out:

1 4 4 5 5 2 2 0

Comparație

De la 10 miliarde de operații la 200 de mii. Diferența este enormă.

Problema 1: maximul după toate operațiile

int suma = 0;
int maxim = 0;

for (int i = 1; i <= n; i++) {
    suma = suma + d[i];
    if (suma > maxim) {
        maxim = suma;
    }
}

fout << maxim;

Problema 2: vectorul nu e inițial 0

Dacă vectorul are valori inițiale v[i], pur și simplu le adunăm la final:

int suma = 0;

for (int i = 1; i <= n; i++) {
    suma = suma + d[i];
    fout << v[i] + suma << " ";
}

Problema 3: câte poziții au valoarea > 0 după toate operațiile?

int suma = 0;
int cnt = 0;

for (int i = 1; i <= n; i++) {
    suma = suma + d[i];
    if (suma > 0) {
        cnt++;
    }
}

fout << cnt;

Problema 4: simulare semafoare

n poziții pe o stradă. Mai multe semafoare acoperă intervale: semafor pe [st, dr] înseamnă “lumină pe acest interval”. Câte poziții sunt luminate de cel puțin un semafor?

Exact aceeași tehnică: fiecare semafor adaugă 1 pe intervalul său. La final, numărăm pozițiile cu valoare > 0.

for (int i = 1; i <= q; i++) {
    int st, dr;
    fin >> st >> dr;
    d[st] = d[st] + 1;
    d[dr + 1] = d[dr + 1] - 1;
}

int suma = 0;
int cnt = 0;

for (int i = 1; i <= n; i++) {
    suma = suma + d[i];
    if (suma > 0) cnt++;
}

fout << cnt;

Vizualizare: ce se întâmplă în vectorul d

Operatie: +3 pe [2, 5]

d:  0  +3   0   0   0  -3   0   0
    ↑   ↑               ↑
    |   |               anulează efectul după poziția 5
    |   începem adunarea de la poziția 2
    poziția 1 nu e afectată

Sume partiale: 0  3  3  3  3  0  0  0   ✓

Fiecare +val la d[st] “pornește” adunarea. Fiecare -val la d[dr+1] o “oprește”.

Greșeli frecvente

1. Uitarea lui d[dr + 1] -= val

Fără scădere, efectul adunării se propagă până la sfârșitul vectorului:

Doar d[2] += 3:
Sume partiale: 0  3  3  3  3  3  3  3   GRESIT!

2. Vectorul d prea mic

Facem d[dr + 1], deci dacă dr poate fi n, avem nevoie de poziția n + 1. Declarăm d[n + 2] ca să fim siguri.

int d[100002]; // n + 2 pozitii

3. Uitarea sumelor parțiale

Vectorul d nu conține direct rezultatul! Trebuie să calculăm sumele parțiale:

// GRESIT:
fout << d[i]; // asta e diferenta, nu valoarea finala

// CORECT:
suma = suma + d[i];
fout << suma;

4. Aplicarea pe vector indexat de la 0

Dacă indexezi de la 0, atenție că d[dr + 1] poate fi d[n] (ultima poziție), nu în afara vectorului.

Ce să reții

• Șmenul lui Mars face adunări pe intervale în O(1) per operație.
• Marcăm: d[st] += val și d[dr + 1] -= val.
• La final, sumele parțiale peste d dau vectorul rezultat.
• Complexitate totală: O(q + n) în loc de O(q * n).
• Vectorul d trebuie să aibă n + 2 poziții.
• Funcționează și pe vectori cu valori inițiale (le adunăm la final).
• Este una dintre cele mai elegante tehnici din informatică.

Probleme

pbinfoTwoop→

pbinfoEasyquery→

pbinfoTv→

pbinfoPaint→

pbinfoMars→