Sume parțiale — AlgoClar

De ce contează?

Pe o autostradă cu borne kilometrice, ca să afli distanța dintre kilometrul 30 și 80 nu mergi pas cu pas — scazi: 80 − 30 = 50. Sumele parțiale fac la fel cu un vector: reții „kilometrajul" cumulat și afli suma oricărui interval printr-o singură scădere.

Ideea: precalculezi o dată, răspunzi instant

Dacă ai multe întrebări „cât e suma elementelor de la poziția st la dr?", a le calcula de fiecare dată costă O(n) per întrebare. Sumele parțiale precalculează o singură dată un vector S, unde S[i] = suma primelor i elemente. Apoi orice interval se află prin scădere.

Construirea vectorului de sume parțiale

Cu indexare de la 1: S[0] = 0, iar S[i] = S[i-1] + v[i].

S	0	5	8	16	17	26
i	0	1	2	3	4	5

Pentru v = {5, 3, 8, 1, 9} (poziții 1..5): S[i] cumulează. S[3] = 5+3+8 = 16. S[0] = 0 e neutrul pentru scădere.

Suma pe interval printr-o scădere

Suma pe [st, dr] = S[dr] − S[st−1]. Exemplu pentru v = {5, 3, 8, 1, 9}, intervalul [2, 4]:

S[4] − S[1] = 17 − 5 = 12 (adică 3 + 8 + 1)

Implementare C++

#include <iostream>
using namespace std;

int main() {
    int n;
    cin >> n;
    long long v[1001], S[1001];
    S[0] = 0;
    for (int i = 1; i <= n; i++) {
        cin >> v[i];
        S[i] = S[i - 1] + v[i];     // suma cumulata
    }

    int q;
    cin >> q;                       // numarul de interogari
    while (q--) {
        int st, dr;
        cin >> st >> dr;
        cout << S[dr] - S[st - 1] << "\n";   // suma pe [st, dr] in O(1)
    }
    return 0;
}

Observația-cheie

Indexarea de la 1 și S[0] = 0 nu sunt întâmplătoare: fac formula S[dr] − S[st−1] să meargă și pentru st = 1 (unde S[0] = 0). Cu indexare de la 0 ai nevoie de un caz special — de aceea sumele parțiale se scriu aproape mereu cu indexare de la 1.

Complexitate

Etapă	Timp	Spațiu
precalculare	O(n)	O(n)
o interogare	O(1)	—
q interogări (naiv)	O(q·n)	O(1)

Pentru q interogări: cu sume parțiale O(n + q), naiv O(q·n). Câștigul e uriaș la multe interogări.

Vizualizare

Urmărește cum vectorul de sume parțiale se construiește cumulativ și cum un interval se obține prin scădere:

Indiciu

Observă că suma unui interval e diferența a două bare cumulate. Cu cât intervalul e mai „la dreapta", cu atât ambele bare sunt mai înalte — dar diferența rămâne suma cerută.

Greșeli frecvente

Capcane reale la sume parțiale:

Formula S[dr] − S[st]: corect e S[dr] − S[st−1], altfel pierzi elementul de pe poziția st.
Lipsa lui S[0] = 0: fără el, intervalul care începe de la 1 dă rezultat greșit sau accesezi S[-1].
Overflow: suma cumulată crește rapid; folosește long long pentru S.
Amesteci indexarea: pornești v de la 0 dar S de la 1 (sau invers) → formule decalate. Fixează o convenție și ține-te de ea.

De reținut

S[i] = suma primelor i elemente; S[i] = S[i-1] + v[i], cu S[0] = 0.
Suma pe [st, dr] = S[dr] − S[st−1], în O(1) după precalculare O(n).
Indexare de la 1 + long long; câștigi enorm la multe interogări.