Sume parțiale (Prefix Sums)

Una dintre cele mai puternice tehnici cu vectori este vectorul sumelor parțiale. Cu el, putem calcula suma oricărui interval [st, dr] instantaneu, fără să parcurgem elementele.

Problema de bază

Avem un vector v cu n elemente și primim q întrebări de forma:

Care este suma elementelor de la poziția st la poziția dr?

Abordarea directă: pentru fiecare întrebare, parcurgem de la st la dr și adunăm. Dacă avem q întrebări, facem q * n operații în cel mai rău caz.

Cu sume parțiale: precalculăm un vector ajutător și răspundem la fiecare întrebare în O(1) - o singură operație.

Ce este vectorul de sume parțiale?

Definim vectorul sp unde:

sp[i] = suma primelor i elemente = v[1] + v[2] + ... + v[i]

Exemplu

v:   3   1   4   1   5   9   2   6
sp:  3   4   8   9  14  23  25  31

Cum construim vectorul?

Formula simplă:

sp[i] = sp[i - 1] + v[i]

Fiecare sumă parțială este suma anterioară plus elementul curent.

sp[0] = 0; // conventie: suma pe 0 elemente = 0

for (int i = 1; i <= n; i++) {
    sp[i] = sp[i - 1] + v[i];
}

Cum calculăm suma pe un interval?

suma(st, dr) = sp[dr] - sp[st - 1]

Aceasta este formula cheie. Suma elementelor de la st la dr este diferența între două sume parțiale.

De ce funcționează?

sp[dr]     = v[1] + v[2] + ... + v[st-1] + v[st] + ... + v[dr]
sp[st-1]   = v[1] + v[2] + ... + v[st-1]

sp[dr] - sp[st-1] = v[st] + v[st+1] + ... + v[dr]

Scădem “începutul” și rămânem exact cu intervalul dorit.

Exemplu

v:   3   1   4   1   5   9   2   6
sp:  3   4   8   9  14  23  25  31

Suma pe intervalul [3, 6] = sp[6] - sp[2] = 23 - 4 = 19

Verificare: v[3] + v[4] + v[5] + v[6] = 4 + 1 + 5 + 9 = 19

Codul complet

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

int v[100001];
long long sp[100001];
int n, q;

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

    for (int i = 1; i <= n; i++) {
        fin >> v[i];
    }

    // Construim sumele partiale
    sp[0] = 0;
    for (int i = 1; i <= n; i++) {
        sp[i] = sp[i - 1] + v[i];
    }

    // Răspundem la întrebări
    for (int i = 1; i <= q; i++) {
        int st, dr;
        fin >> st >> dr;
        fout << sp[dr] - sp[st - 1] << "\n";
    }

    return 0;
}

date.in:

8 3
3 1 4 1 5 9 2 6
1 8
3 6
5 5

date.out:

31
19
5

Comparație: cu și fără sume parțiale

Cu sume parțiale, răspundem la 100.000 de întrebări în timp aproape instantaneu.

Problema 1: câte subsecvențe au suma egală cu S?

Parcurgem toate perechile (st, dr) și verificăm suma folosind sp:

int cnt = 0;

for (int st = 1; st <= n; st++) {
    for (int dr = st; dr <= n; dr++) {
        if (sp[dr] - sp[st - 1] == s) {
            cnt++;
        }
    }
}

fout << cnt;

Fără sume parțiale, calculul sumei în bucla interioară ar costa încă O(n). Cu sp, fiecare verificare este O(1).

Problema 2: subsecvența de lungime K cu suma maximă

Găsim secvența de exact K elemente consecutive care are suma maximă.

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

int v[100001];
long long sp[100001];
int n, k;

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

    for (int i = 1; i <= n; i++) {
        fin >> v[i];
    }

    sp[0] = 0;
    for (int i = 1; i <= n; i++) {
        sp[i] = sp[i - 1] + v[i];
    }

    long long maxSuma = sp[k] - sp[0]; // prima fereastra
    int pozMax = 1;

    for (int st = 2; st + k - 1 <= n; st++) {
        int dr = st + k - 1;
        long long suma = sp[dr] - sp[st - 1];

        if (suma > maxSuma) {
            maxSuma = suma;
            pozMax = st;
        }
    }

    fout << "Suma maxima: " << maxSuma << endl;
    fout << "Incepe la pozitia: " << pozMax;

    return 0;
}

date.in:

8 3
3 1 4 1 5 9 2 6

date.out:

Suma maxima: 16
Incepe la pozitia: 5

Secvența v[5], v[6], v[7] = 5 + 9 + 2 = 16.

Problema 3: echilibrare - punctul de tăiere

Găsim poziția k astfel încât suma primelor k elemente să fie cât mai apropiată de suma ultimelor n - k elemente.

for (int k = 1; k < n; k++) {
    long long stanga = sp[k];
    long long dreapta = sp[n] - sp[k];
    // ...
}

Cu sume parțiale, fiecare calcul este O(1).

Greșeli frecvente

1. Uitarea lui sp[0] = 0

Fără această inițializare, sp[dr] - sp[st - 1] dă rezultat greșit când st = 1.

2. Formula greșită

// GRESIT:
sp[dr] - sp[st]      // lipseste v[st] din suma!

// CORECT:
sp[dr] - sp[st - 1]  // include v[st]

3. Depășire la int

Dacă elementele pot fi până la 10^5 și n până la 10^5, suma poate ajunge la 10^10 - depășește int. Folosește long long pentru sp.

4. Confuzia între v și sp

• v[i] = elementul de pe pozitia i
• sp[i] = suma primelor i elemente

Nu le amesteca în formule.

Ce să reții

• Sumele parțiale permit calculul sumei pe orice interval în O(1).
• Formula: suma(st, dr) = sp[dr] - sp[st - 1].
• Construirea: sp[i] = sp[i - 1] + v[i], cu sp[0] = 0.
• Folosește long long pentru sume mari.
• Este una dintre cele mai folosite tehnici la concursuri.
• Orice problemă cu “suma pe interval” sau “subsecvență cu sumă” beneficiază de sume parțiale.

Probleme

pbinfoSumainsecv→

pbinfoSecvk→

pbinfoSumesecv1→