Sume parțiale — răspunde instant la „cât e suma de la i la j?”

De ce contează?

Ții un caiet în care notezi în fiecare seară cât ai cheltuit, dar și totalul de la începutul lunii până azi. Dacă vrei să afli cât ai cheltuit între ziua 5 și ziua 12, nu mai aduni nimic: iei totalul din ziua 12 și scazi totalul din ziua 4. O scădere, gata. Asta sunt sumele parțiale.

Problema

Ai un vector și ți se pun multe întrebări de forma: „cât e suma elementelor de la poziția i la poziția j?”. Dacă pentru fiecare întrebare aduni de la i la j, o întrebare costă O(n). La multe întrebări (Q) devine O(Q·n) — prea lent.

Observația-cheie

Ideea de precalculare: muncește o singură dată la început (construiești ceva util), apoi fiecare întrebare e instantanee. Plătești O(n) o dată, ca să răspunzi în O(1) de oricâte ori.

Vectorul de sume parțiale

Definim s[i] = suma primelor i elemente:

s[0] = 0, s[i] = s[i-1] + v[i].

Lucrăm cu vectorul indexat de la 1 ca să avem s[0] = 0 (suma a zero elemente) — asta face formula finală curată.

Atunci suma pe intervalul [i, j] este:

suma(i, j) = s[j] - s[i-1]

Pas cu pas pe numere

Fie v = {3, 1, 4, 1, 5, 9} (indici 1..6).

v	3	1	4	1	5	9
	1	2	3	4	5	6

Vectorul original, indexat de la 1.

Construim s adunând pe rând:

s	0	3	4	8	9	14	23
	0	1	2	3	4	5	6

s[i] = s[i-1] + v[i]. Ex: s[3] = 4 + 4 = 8.

Vrem suma de la poziția 2 la 5 (adică 1 + 4 + 1 + 5 = 11):

suma(2, 5) = s[5] - s[1] = 14 - 3 = 11. ✓

s	0	3	4	8	9	14	23
	0	1	2	3	4	5	6

suma(2,5) = s[5] - s[1] = 14 - 3 = 11. O singură scădere.

Implementare C++

#include <iostream>
using namespace std;

const int N = 100;
long long s[N + 1]; // long long: sumele pot depasi int

int main() {
    int v[] = {0, 3, 1, 4, 1, 5, 9}; // v[0] nefolosit, lucram de la 1
    int n = 6;

    s[0] = 0;
    for (int i = 1; i <= n; i++)
        s[i] = s[i - 1] + v[i]; // precalculare O(n)

    // raspunsuri O(1) fiecare:
    int i = 2, j = 5;
    cout << s[j] - s[i - 1] << "\n"; // 11

    i = 1; j = 6;
    cout << s[j] - s[i - 1] << "\n"; // 23 (suma totala)
    return 0;
}

Complexitate

Etapă	Timp
Construire `s`	O(n), o singură dată
Fiecare întrebare	O(1)
Total pentru Q întrebări	O(n + Q)

Comparativ cu metoda naivă O(n·Q), câștigul e enorm când ai multe întrebări.

Greșeli frecvente

Greșeli frecvente de concurs:

Overflow. Suma multor numere mari depășește int. Folosește long long pentru vectorul s. E greșeala numărul unu la sume parțiale.
s[i] în loc de s[i-1]. Formula corectă e s[j] - s[i-1]. Dacă scrii s[j] - s[i], pierzi exact elementul v[i] de la începutul intervalului.
Indexare de la 0 fără grijă. Dacă lucrezi de la 0, ai nevoie de un caz special pentru i = 0 (nu există s[-1]). De-asta indexarea de la 1 cu s[0] = 0 e mai sigură.
Reconstruiești s la fiecare întrebare. Sensul tehnicii e să construiești s o singură dată. Dacă o refaci mereu, ai pierdut tot avantajul.

Vizualizare

Urmărește cum se construiește vectorul de sume parțiale și cum o întrebare devine o scădere:

Indiciu

Citește s[i] ca „totalul de până aici”. Suma unui interval = „totalul la final” minus „totalul de dinainte de început”.

Recapitulare

s[i] = suma primelor i elemente; o construiești o dată în O(n).
Orice sumă pe interval devine o singură scădere: s[j] - s[i-1], în O(1).
Folosește long long pentru s și ai grijă la i-1, nu i.