Sume partiale. Suma elementelor dintr-o submatrice in C++

Algoritmul "naiv" (nerecomandat!)

După ce citim datele de intrare, inițializăm o variabilă sum = 0 şi parcurgem toate numerele din şir cu indicii de la x la y, adunând elementele pe rând. Complexitatea soluției este O(n). Soluția este bună pentru doar câteva calculări, dar de obicei, în probleme, se cer foarte multe calculări şi atunci soluția iese din timp.

int n, a[MAX + 1], x, y, sum = 0; //Declarăm variabilele//pentru mai multe detalii: https://100din100.netlify.app

//Citim datele de intrare//pentru mai multe detalii: https://100din100.netlify.app
fin>>n;
for(int i = 1; i <= n; i++)
	fin>>a[i];
fin>>x>>y;

//Prelucrăm în O(n) suma numerelor//pentru mai multe detalii: https://100din100.netlify.app
for(int i = x; i <= y; i++)
	sum += a[i];

//Afişăm//pentru mai multe detalii: https://100din100.netlify.app
fout<<sum;
						

ALGORITMUL EFICIENT

Dacă vrem să aflăm suma elementelor cu indicii de la x la y, este acelaşi lucru ca şi când am afla suma elementelor de la 1 la y, din care scădem suma primelor x - 1 numere:

a[3] + a[4] + a[5] = (a[1] + a[2] + a[3] + a[4] + a[5]) - (a[1] + a[2])

a[x] + a[x+1] + … + a[y] = a[1] + a[2] + … + a[y] - (a[1] + a[2] + … + a[x-1])

Dacă vrem să aflăm suma elementelor de la 1 la x, putem afla răspunsul în timp ce citim numerele, creând un alt vector, s[], în care s[i] este:

• 0, pentru i = 0
• a[i] + s[i - 1] (elementul curent + suma elementelor anterioare), pentru 1 ≤ i ≤ n

Astfel se poate afla în O(1) suma elementelor dintre oricare indici.

i	1	2	3	4	5	6
a[i]	4	7	3	6	4	2
s[i]	4	11	14	20	24	26

a[3] + a[4] + a[5] = s[5] - s[3 - 1]

a[3] + a[4] + a[5] = s[5] - s[2]

Iată codul în C++:

int n, a[MAX + 1], s[MAX + 1], x, y, sum = 0; //Declarăm variabilele//pentru mai multe detalii: https://100din100.netlify.app
s[0] = 0;

//Citim datele de intrare//pentru mai multe detalii: https://100din100.netlify.app
fin>>n;
for(int i = 1; i <= n; i++) {
	fin>>a[i];
	s[i] = a[i] + s[i - 1];
}
fin>>x>>y;

//Afişăm//pentru mai multe detalii: https://100din100.netlify.app
fout<<s[y] - s[x - 1];
						

Desigur, în unele situații, precum aceasta, nu mai avem nevoie de vectorul a. Partea de citire devine:

//Citim datele de intrare//pentru mai multe detalii: https://100din100.netlify.app
fin>>n;
for(int i = 1; i <= n; i++) {
	fin>>s[i];
	s[i] += s[i - 1];
}
fin>>x>>y;
						

Exemplu

Iată un exemplu de problemă rezolvată:

CERINȚĂ Dându-se două numere naturale nenule, n şi m (n, m ≤ 100), precum şi o matrice de n linii şi m coloane, răspundeți la q întrebări de forma "i‎1 j1 i2 j2" cu semnificația "Care este suma elementelor din submatricea cu colțurile (i‎1, j1) (stânga-sus), (i2, j2) (dreapta-jos)?".
DATE DE INTRARE Pe prima linie a testului se află două numere, n şi m. Pe următoarele n linii se află m numere întregi, care încap în tipul de date int. Pe următoarea linie se află numărul q, iar pe următoarele q linii se află cele 4 variabile corespunzătoare unei întrebări.
DATE DE IEŞIRE Pe prima linie, q valori cu semnificația din cerință (răspunsul la întrebări).

Rezolvare pas cu pas.

#include <iostream>
#define MAX 100

using namespace std;

//Declarăm variabilele//pentru mai multe detalii: https://100din100.netlify.app
int n, m, q, i‎1, i2, j1, j2;
long long s[MAX + 1][MAX + 1];
//Atenție, dacă toate elementele matricii sunt INT_MAX,//pentru mai multe detalii: https://100din100.netlify.app
//sau o valoare foarte mare, atunci suma poate ieşi din//pentru mai multe detalii: https://100din100.netlify.app
//int. Cel mai rău caz: 100 * 100 * INT_MAX.//pentru mai multe detalii: https://100din100.netlify.app

int main() {
	//Citim datele de intrare//pentru mai multe detalii: https://100din100.netlify.app
	cin>>n>>m;
	for(int i = 1; i <= n; i++) {
		for(int j = 1; j <= m; j++) {
			cin>>s[i][j];
			s[i][j] += s[i - 1][j] + s[i][j - 1] - s[i - 1][j - 1];
		}
	}
	cin>>q;
	for(int i = 1; i <= q; i++) {
		cin>>i‎1>>j1>>i2>>j2;
		cout<<s[i2][j2] - s[i‎1 - 1][j2] - s[i2][j1 - 1] + s[i‎1 - 1][j1 - 1]<<" ";
	}
	return 0;
}
						

Pe vector

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

Pe matrice

s[i][j] = a[i][j] + s[i - 1][j] + s[i][j - 1] - s[i - 1][j - 1];
suma(i‎1, j1, i2, j2) = s[i2][j2] - s[i‎1 - 1][j2] - s[i2][j1 - 1] + s[i‎1 - 1][j1 - 1];