Sume parțiale în C++. Probleme cu sume parțiale
Sumele parțiale reprezintă o noțiune pe cât de simplă, pe atât de utilă. Ele sunt folosite într-o grămadă de probleme de informatică, așa că în acest articol voi prezenta cele mai importante tehnici ce folosesc conceptul de sume parțiale.
Definiție
Fie un vector de numere indexate de la Vectorului îi vom asocia un șir cu proprietatea:
Acest șir se numește șirul sumelor parțiale ale lui De aici și notația (partial sums). Deci, reprezintă suma primelor elemente ale vectorului dat, adică a a sumă parțială a lui Prin convenție, pentru că este elementul neutru la adunare. Șirul poate fi calculat foarte ușor în timp liniar bazându-ne pe următoarea relație de recurență:
Această recurență face construcția șirului de sume parțiale să poată fi considerată o problemă de programare dinamică. Desigur, una foarte simplă.
vector<int> ps(n + 1);for (int i = 1; i <= n; i++) ps[i] = ps[i - 1] + v[i];
Aplicații
Putem trece deja la aplicații! Am încercat să aleg 6 probleme clasice prin care să ilustrez cât mai multe tehnici ce folosesc conceptul de sume parțiale.
Problema 1.
Se dă un vector cu numere întregi, precum și întrebări de forma cu semnificația: Care este suma elementelor din cuprinse între indicii și Să se răspundă eficient la cele întrebări.
Asta e probabil cea mai cunoscută problemă de sume parțiale, și cred că de aici a și apărut nevoia de acest concept. Evident, o soluție ar fi să parcurgem secvența corespunzătoare fiecărei întrebare, însă am avea o complexitate de ordinul Soluția liniară se obține observând următorul lucru: Suma elementelor din secvența determinată de indicii și este egală cu Deci, după ce citim vectorul sau chiar în timpul citirii, construim șirul iar apoi răspundem la fiecare întrebare în folosind această formulă. Astfel, obținem complexitatea
int n; cin >> n;vector<int> ps(n + 1);for (int i = 1; i <= n; i++) { int x; cin >> x; ps[i] = ps[i - 1] + x;}
int q; cin >> q;for (int i = 0; i < q; i++) { int x, y; cin >> x >> y; cout << ps[y] - ps[x - 1] << '\n';}
Problema 2.
Se dă un număr natural și un vector cu numere naturale. Atât cât și suma elementelor lui sunt mai mici sau egale cu Să se determine o secvență a lui cu proprietatea că suma elementelor ei este egală cu
Pentru a obține o soluție liniară, ne bazăm pe faptul că dacă o secvență are suma elementelor atunci Deci, dacă există vreo astfel de secvență care să aibă capătul din dreapta în atunci trebuie să existe și un indice pentru care Putem găsi rapid un astfel de indice în timpul calculării sumelor parțiale folosind un vector suplimentar În vom reține un indice găsit până la pasul curent, astfel încât sau dacă încă n-am găsit un astfel de indice.
Dacă la pasul am obținut o sumă parțială pentru care afișăm indicii și după care ne oprim. Trebuie să avem grijă ca nu cumva să uităm de În acest sens, la început trebuie să inițializăm cu valoarea
vector<int> pos(1e6 + 1, -1);int ps = 0;pos[0] = 0;int n; cin >> n;for (int i = 1; i <= n; i++) { int x; cin >> x; ps += x; if (ps - k >= 0 && pos[ps - k] != -1) { cout << pos[ps - k] + 1 << ' ' << i << '\n'; return 0; } pos[ps] = i;}
Problema 3.
Se dă un număr și un vector cu elemente. Atât cât și elementele lui sunt numere naturale, până în Să se determine o secvență a lui cu proprietatea că suma elementelor ei este egală cu
Aproape aceeași problemă cu cea precedentă, doar că acum numerele din pot lua valori egale cu un miliard, motiv pentru care sumele parțiale pot ieși din tipul int
, așa că sigur nu putem folosi ideea cu vectorul Bine, dacă e să fim try-hard, putem înlocui vectorul din urmă cu un tabel de hashing (care cam trebuie făcut de mână), dar hai să vedem totuși o altă idee, suficient de rapidă.
Elementele lui sunt în continuare numere naturale, ceea ce ne garantează monotonia șirului Diferența dintre doi termeni consecutivi ai lui este nenegativă, de unde șirul este crescător. Ei bine, monotonia lui ne duce cu gândul la faptul că putem folosi căutare binară. Așadar, pentru fiecare indice căutăm binar cel mai din stânga indice cu proprietatea că Dacă obținem un indice pentru care diferența dintre cele două sume parțiale este egală cu înseamnă că am găsit secvența căutată.
vector<int> ps(n + 1);for (int i = 1; i <= n; i++) ps[i] = ps[i - 1] + v[i];for (int j = 1; j <= n; j++) { int lo = -1, hi = j; while (hi - lo > 1) { int md = (lo + hi) / 2; if (ps[j] - ps[md] > k) lo = md; else hi = md; } if (ps[j] - ps[hi] == k) { cout << hi + 1 << ' ' << j << '\n'; return 0; }}
Dacă ne gândim puțin, putem folosi fără probleme funcția lower_bound
din STL, căutarea binară fiind până la urmă pe un vector, nu pe o funcție:
vector<int> ps(n + 1);for (int i = 1; i <= n; i++) ps[i] = ps[i - 1] + v[i];for (int j = 1; j <= n; j++) { int i = lower_bound(ps.begin(), ps.begin() + j, ps[j] - k) - ps.begin(); if (ps[j] - ps[i] == k) { cout << i + 1 << ' ' << j << '\n'; return 0; }}
O problemă în care am folosit ideea de căutare binară pe șirul sumelor parțiale este br.
Problema 4.
Se dă un vector cu elemente numere naturale. Să se determine o secvență a lui astfel încât suma elementelor ei să fie divizibilă cu
Vom construi din nou șirul sumelor parțiale ale lui dar de această dată le vom calcula modulo Deci, Astfel, ne va da restul împărțirii la a sumei elementelor secvenței Noi vrem ca acest rest să fie deci și trebuie să fie egale (modulo
Așadar, trebuie doar să căutăm doi indici și pentru care Întrebarea este: Vor exista întotdeauna doi astfel de indici? Da, conform principiului lui Dirichlet. Acesta ne spune că dacă alegem elemente dintr-o mulțime cu elemente, atunci sigur vor exista măcar două elemente egale. În cazul nostru, alegem elemente pentru că avem sume parțiale, iar mulțimea din care alegem elementele este mulțimea resturilor modulo care clar are elemente:
Pentru a găsi ușor un indice astfel încât vom folosi din nou ideea cu vectorul de la problema 2.
vector<int> pos(n + 1, -1);int ps = 0;pos[0] = 0;int n; cin >> n;for (int i = 1; i <= n; i++) { int x; cin >> x; ps = (ps + x) % n; if (pos[ps] != -1) { cout << pos[ps] + 1 << ' ' << i << '\n'; return 0; } pos[ps] = i;}
Problema 5.
Se dă o matrice cu linii și coloane. Să se determine suma maximă a elementelor unei submatrice a lui cu linii și coloane.
Vom nota cu suma elementelor submatricei cu colțurile stânga-sus și dreapta-jos în și respectiv În total avem submatrice cu linii și coloane – câte una pentru fiecare celulă cu și Dacă ar fi să parcurgem fiecare astfel de submatrice ca să-i calculăm suma, am obține complexitatea Însă, putem afla suma elementelor unei submatrice în precalculând niște sume parțiale 2D: În reținem Relația de recurență este:
Practic, prin adunăm iar prin adunăm Dacă îl mai adunăm și pe e aproape gata, doar că pe l-am adunat de două ori, motiv pentru care trebuie să-l scădem pe
Acum că avem calculate aceste sume parțiale, putem determina folosind următoarea formulă:
Justificarea e similară cu cea de mai devreme: Scădem două porțiuni de care n-avem nevoie, dar pentru că l-am scăzut de două ori pe îl adunăm înapoi. Iată și un desen, sugestiv sper eu:
Astfel, am obținut un algoritm optim, de complexitate Iată și codul:
vector ps(m + 1, vector<int>(n + 1));for (int i = 1; i <= m; i++) for (int j = 1; j <= n; j++) ps[i][j] = ps[i - 1][j] + ps[i][j - 1] - ps[i - 1][j - 1] + a[i][j];
int ans = 0;for (int i1 = 1, i2 = x; i2 <= m; i1++, i2++) for (int j1 = 1, j2 = y; j2 <= n; j1++, j2++) ans = max(ans, ps[i2][j2] - ps[i1 - 1][j2] - ps[i2][j1 - 1] + ps[i1 - 1][j1 - 1]);cout << ans << '\n';
Problema 6.
Se dă un vector cu elemente din mulțimea Să se determine numărul de secvențe ale lui ce conțin de două ori mai mulți de decât de
Asta e o problemă pe care tocmai am propus-o pe PbInfo; o puteți trimite aici. Ideea am întâlnit-o într-o problemă de ONI pe care am rezolvat-o mai demult, doar că acolo apărea într-un context mult mai complex.
Ca de obicei, construim șirul sumelor parțiale ale lui Observația de bază este că dacă o secvență îndeplinește condiția din enunț, atunci Adică numărul de din secvența este înmulțit cu lungimea secvenței. Dacă trecem termenii care depind de în stânga, iar pe cei care depind de în dreapta, obținem
Asta înseamnă că numărul secvențelor căutate care se termină în este egal cu numărul indicilor ce verifică relația de mai sus. Prin urmare, soluția este ca în timp ce calculăm sumele parțiale ale lui să reținem într-un vector de frecvență de câte ori am obținut suma până la pasul curent. Cum pentru fiecare se efectuează o interogare și o actualizare în vectorul de frecvență, ambele în timp constant, complexitatea finală devine
În timpul implementării trebuie să fim atenți la trei detalii:
- Răspunsul este de ordinul (la fel ca numărul de secvențe ale lui așa că trebuie reținut într-o variabilă de tipul
long long int
. - Înainte să analizăm fiecare posibil, trebuie să actualizăm frecvența lui
- Valorile pot fi și negative, așa că vectorul de frecvență trebuie decalat cu poziții la dreapta, unde este valoarea minimă ce poate fi obținută. Aceasta este și se atinge atunci când și Valoarea maximă este și se atinge când și
int n; fin >> n;vector<int> frq(3 * n + 1);frq[n] = 1;int ps = 0;int64_t sol = 0;for (int i = 1; i <= n; i++) { bool x; fin >> x; ps += x; sol += frq[2 * i - 3 * ps + n]++;}fout << sol << '\n';
Alte operații?
Cred că v-am convins că sumele parțiale sunt foarte utile, dar le putem folosi oare și pentru alte operații? De exemplu, putem ca în loc de sume parțiale să facem minime parțiale? Răspunsul este că depinde de tipul operației.
Dacă operația este reversibilă, putem calcula suma elementelor oricărei secvențe a vectorului nostru bazându-ne pe sume parțiale. (Aici prin suma pe o secvență mă refer la Să presupunem că Operația se numește reversibilă dacă putem atât să calculăm cât și să facem inversa acestei operații, și anume dacă știm rezultatul și unul dintre termeni să îl aflăm pe celălalt termen Două operații comune care au proprietatea de a fi reversibile sunt adunarea și disjuncția exclusivă
Printre operațiile care nu sunt reversibile se numără și Din păcate, nu putem calcula suma pe secvențe pentru aceste operații folosind tehnica sumelor parțiale. Pentru a rezolva problema asta există structuri de date mai avansate, cum ar fi Sparse Tables. Însă, putem calcula minime, maxime și uri pe prefixe și sufixe fără nicio problemă.
Probleme recomandate
Pe lângă problemele din acest articol, pe care în marea lor parte le puteți găsi pe PbInfo, puteți lucra următoarele probleme de pe InfoArena:
Recomand să citiți și articolul despre tehnica Two-Pointers, prin intermediul căreia putem rezolva mai ușor cazuri particulare ale unor probleme din acest articol. Dacă aveți vreo întrebare legată de sume parțiale, nu ezitați să o lăsați într-un comentariu mai jos, pentru a vă putea ajuta