Sume parțiale în C++. Probleme cu sume parțiale

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 vv un vector de nn numere indexate de la 11 Vectorului vv îi vom asocia un șir ps\mathrm{ps} cu proprietatea:

ps[i]=v[1]+v[2]++v[i]\mathrm{ps}[i] = v[1] + v[2] + \cdots + v[i]

Acest șir se numește șirul sumelor parțiale ale lui vv De aici și notația (partial sums). Deci, ps[i]\mathrm{ps}[i] reprezintă suma primelor ii elemente ale vectorului dat, adică a iia sumă parțială a lui vv Prin convenție, ps[0]=0\mathrm{ps}[0] = 0 pentru că 00 este elementul neutru la adunare. Șirul ps\mathrm{ps} poate fi calculat foarte ușor în timp liniar bazându-ne pe următoarea relație de recurență:

ps[i]={ps[i1]+v[i]pentru 1in0pentru i=0\mathrm{ps}[i] = \begin{cases} \mathrm{ps}[i - 1] + v[i] & \text{pentru } 1 \le i \le n\\ 0 & \text{pentru } i = 0 \end{cases}

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 vv cu nn numere întregi, precum și qq întrebări de forma x yx \text{ } y cu semnificația: Care este suma elementelor din vv cuprinse între indicii xx și yy Să se răspundă eficient la cele qq î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 O(qn)O(q \cdot n) Soluția liniară se obține observând următorul lucru: Suma elementelor din secvența determinată de indicii xx și yy este egală cu ps[y]ps[x1]\mathrm{ps}[y] - \mathrm{ps}[x - 1] Deci, după ce citim vectorul vv sau chiar în timpul citirii, construim șirul ps\mathrm{ps} iar apoi răspundem la fiecare întrebare în O(1)O(1) folosind această formulă. Astfel, obținem complexitatea O(n+q)O(n + q)

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 kk și un vector vv cu nn numere naturale. Atât kk cât și suma elementelor lui vv sunt mai mici sau egale cu 10610^6 Să se determine o secvență a lui vv cu proprietatea că suma elementelor ei este egală cu kk

Pentru a obține o soluție liniară, ne bazăm pe faptul că dacă o secvență [x+1,y][x + 1, y] are suma elementelor kk atunci ps[y]ps[x]=k\mathrm{ps}[y] - \mathrm{ps}[x] = k Deci, dacă există vreo astfel de secvență care să aibă capătul din dreapta în yy atunci trebuie să existe și un indice x<yx \lt y pentru care ps[x]=ps[y]k\mathrm{ps}[x] = \mathrm{ps}[y] - k Putem găsi rapid un astfel de indice în timpul calculării sumelor parțiale folosind un vector suplimentar pos\mathrm{pos} În pos[i]\mathrm{pos}[i] vom reține un indice x0x \ge 0 găsit până la pasul curent, astfel încât ps[x]=i\mathrm{ps}[x] = i sau 1-1 dacă încă n-am găsit un astfel de indice.

Dacă la pasul ii am obținut o sumă parțială psps pentru care pos[psk]1\mathrm{pos}[ps - k] \neq -1 afișăm indicii pos[ps]+1\mathrm{pos}[ps] + 1 și ii după care ne oprim. Trebuie să avem grijă ca nu cumva să uităm de ps[0]\mathrm{ps}[0] În acest sens, la început trebuie să inițializăm pos[0]\mathrm{pos}[0] cu valoarea 00

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 k>0k \gt 0 și un vector vv cu nn elemente. Atât kk cât și elementele lui vv sunt numere naturale, până în 10910^9 Să se determine o secvență a lui vv cu proprietatea că suma elementelor ei este egală cu kk

Aproape aceeași problemă cu cea precedentă, doar că acum numerele din vv 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 pos\mathrm{pos} 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 vv sunt în continuare numere naturale, ceea ce ne garantează monotonia șirului ps\mathrm{ps} Diferența dintre doi termeni consecutivi ai lui ps\mathrm{ps} este nenegativă, de unde șirul este crescător. Ei bine, monotonia lui ps\mathrm{ps} ne duce cu gândul la faptul că putem folosi căutare binară. Așadar, pentru fiecare indice j1j \ge 1 căutăm binar cel mai din stânga indice i<ji \lt j cu proprietatea că ps[j]ps[i]k\mathrm{ps}[j] - \mathrm{ps}[i] \le k Dacă obținem un indice pentru care diferența dintre cele două sume parțiale este egală cu kk î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 vv cu nn elemente numere naturale. Să se determine o secvență a lui vv astfel încât suma elementelor ei să fie divizibilă cu nn

Vom construi din nou șirul sumelor parțiale ale lui vv dar de această dată le vom calcula modulo nn Deci, ps[i]=(v[1]+v[2]++v[i])modn\mathrm{ps}[i] = (v[1] + v[2] + \cdots + v[i]) \modd n Astfel, ps[j]ps[i]\mathrm{ps}[j] - \mathrm{ps}[i] ne va da restul împărțirii la nn a sumei elementelor secvenței [i+1,j][i + 1, j] Noi vrem ca acest rest să fie 00 deci ps[i]\mathrm{ps}[i] și ps[j]\mathrm{ps}[j] trebuie să fie egale (modulo nn

Așadar, trebuie doar să căutăm doi indici ii și jj pentru care ps[i]=ps[j]\mathrm{ps}[i] = \mathrm{ps}[j] Întrebarea este: Vor exista întotdeauna doi astfel de indici? Da, conform principiului lui Dirichlet. Acesta ne spune că dacă alegem n+1n + 1 elemente dintr-o mulțime cu nn elemente, atunci sigur vor exista măcar două elemente egale. În cazul nostru, alegem n+1n + 1 elemente pentru că avem n+1n + 1 sume parțiale, iar mulțimea din care alegem elementele este mulțimea resturilor modulo nn care clar are nn elemente: {0,1,,n1}\{0, 1, \ldots, n - 1\}

Pentru a găsi ușor un indice i<ji \lt j astfel încât ps[i]=ps[j]\mathrm{ps}[i] = \mathrm{ps}[j] vom folosi din nou ideea cu vectorul pos\mathrm{pos} 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 aa cu mm linii și nn coloane. Să se determine suma maximă a elementelor unei submatrice a lui aa cu xx linii și yy coloane.

Vom nota cu s(i1,j1,i2,j2)s(i_1, j_1, i_2, j_2) suma elementelor submatricei cu colțurile stânga-sus și dreapta-jos în (i1,j1)(i_1, j_1) și respectiv (i2,j2)(i_2, j_2) În total avem (mx+1)(ny+1)(m - x + 1)(n - y + 1) submatrice cu xx linii și yy coloane – câte una pentru fiecare celulă (i,j)(i, j) cu ixi \ge x și jyj \ge y Dacă ar fi să parcurgem fiecare astfel de submatrice ca să-i calculăm suma, am obține complexitatea O(m2n2)O(m^2 n^2) Însă, putem afla suma elementelor unei submatrice în O(1)O(1) precalculând niște sume parțiale 2D: În ps[i][j]\mathrm{ps}[i][j] reținem s(1,1,i,j)s(1, 1, i, j) Relația de recurență este:

ps[i][j]={ps[i1][j]+ps[i][j1]ps[i1][j1]+a[i][j]pentru i,j10pentru i=0 sau j=0\mathrm{ps}[i][j] = \begin{cases} \mathrm{ps}[i - 1][j] + \mathrm{ps}[i][j - 1] - \mathrm{ps}[i - 1][j - 1] + a[i][j] & \text{pentru } i, j \ge 1\\ 0 & \text{pentru } i = 0 \text{ sau } j = 0 \end{cases}

Practic, prin ps[i1][j]\mathrm{ps}[i - 1][j] adunăm s(1,1,i1,j1)+s(1,j,i1,j)s(1, 1, i - 1, j - 1) + s(1, j, i - 1, j) iar prin ps[i][j1]\mathrm{ps}[i][j - 1] adunăm s(1,1,i1,j1)+s(i,1,i,j1)s(1, 1, i - 1, j - 1) + s(i, 1, i, j - 1) Dacă îl mai adunăm și pe a[i][j]a[i][j] e aproape gata, doar că pe s(1,1,i1,j1)s(1, 1, i - 1, j - 1) l-am adunat de două ori, motiv pentru care trebuie să-l scădem pe ps[i1][j1]\mathrm{ps}[i - 1][j - 1]

Acum că avem calculate aceste sume parțiale, putem determina s(i1,j1,i2,j2)s(i_1, j_1, i_2, j_2) folosind următoarea formulă:

s(i1,j1,i2,j2)=ps[i2][j2]ps[i11][j2]ps[i2][j11]+ps[i11][j11]s(i_1, j_1, i_2, j_2) = \mathrm{ps}[i_2][j_2] - \mathrm{ps}[i_1 - 1][j_2] - \mathrm{ps}[i_2][j_1 - 1] + \mathrm{ps}[i_1 - 1][j_1 - 1]

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 s(1,1,i11,j11)s(1, 1, i_1 - 1, j_1 - 1) îl adunăm înapoi. Iată și un desen, sugestiv sper eu:

Sume parțiale 2D

Astfel, am obținut un algoritm optim, de complexitate O(mn)O(mn) 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 vv cu nn elemente din mulțimea {0,1}\{0, 1\} Să se determine numărul de secvențe ale lui vv ce conțin de două ori mai mulți de 11 decât de 00

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 vv Observația de bază este că dacă o secvență [i+1,j][i + 1, j] îndeplinește condiția din enunț, atunci 3(ps[j]ps[i])=2(ij)3(\mathrm{ps}[j] - \mathrm{ps}[i]) = 2(i - j) Adică numărul de 11 din secvența [x,y][x, y] este 2/32/3 înmulțit cu lungimea secvenței. Dacă trecem termenii care depind de ii în stânga, iar pe cei care depind de jj în dreapta, obținem 2i3ps[i]=2j3ps[j]2i - 3\mathrm{ps}[i] = 2j - 3\mathrm{ps}[j]

Asta înseamnă că numărul secvențelor căutate care se termină în jj este egal cu numărul indicilor i<ji \lt j ce verifică relația de mai sus. Prin urmare, soluția este ca în timp ce calculăm sumele parțiale ale lui vv să reținem într-un vector de frecvență frq\mathrm{frq} de câte ori am obținut suma 2j3ps[j]2j - 3\mathrm{ps}[j] până la pasul curent. Cum pentru fiecare jj se efectuează o interogare și o actualizare în vectorul de frecvență, ambele în timp constant, complexitatea finală devine O(n)O(n)

În timpul implementării trebuie să fim atenți la trei detalii:

  • Răspunsul este de ordinul O(n2)O(n^2) (la fel ca numărul de secvențe ale lui vv așa că trebuie reținut într-o variabilă de tipul long long int.
  • Înainte să analizăm fiecare jj posibil, trebuie să actualizăm frecvența lui ps[0]\mathrm{ps}[0]
  • Valorile 2i3ps[i]2i - 3\mathrm{ps}[i] pot fi și negative, așa că vectorul de frecvență trebuie decalat cu k-k poziții la dreapta, unde kk este valoarea minimă ce poate fi obținută. Aceasta este n-n și se atinge atunci când i=ni = n și ps[n]=n\mathrm{ps}[n] = n Valoarea maximă este 2n2n și se atinge când i=ni = n și ps[n]=0\mathrm{ps}[n] = 0
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 \circ 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ță [i,j][i, j] mă refer la v[i]v[i+1]v[j]v[i] \circ v[i + 1] \circ \cdots \circ v[j] Să presupunem că ab=ca \circ b = c Operația \circ se numește reversibilă dacă putem atât să calculăm aba \circ b cât și să facem inversa acestei operații, și anume dacă știm rezultatul (c\htmlClass{katexified}{(} c și unul dintre termeni (b\htmlClass{katexified}{(} b să îl aflăm pe celălalt termen (a\htmlClass{katexified}{(} a Două operații comune care au proprietatea de a fi reversibile sunt adunarea (+\htmlClass{katexified}{(} + și disjuncția exclusivă (xor\htmlClass{katexified}{(} \mathrm{xor}

Printre operațiile care nu sunt reversibile se numără min\min max\max și cmmdc\mathrm{cmmdc} 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 cmmdc\mathrm{cmmdc}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:

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

Mulțumesc că ai citit acest articol.
Dacă vrei să susții blogul, poți cumpăra un abonament de 2$.

patreon

Lasă un comentariu!

0 comentarii