Având în vedere o matrice de dimensiunea M x N, există un număr mare de interogări pentru a găsi sumele submatricelor. Intrările la interogări sunt indecși stânga sus și dreapta jos ai submatricei a căror sumă este de aflat. 

Cum se preprocesează matricea astfel încât interogările de sumă submatrice să poată fi efectuate în timp O(1). 

Exemplu:

  tli :   Row number of top left of query submatrix   tlj :   Column number of top left of query submatrix   rbi :   Row number of bottom right of query submatrix   rbj :   Column number of bottom right of query submatrix Input: mat[M][N] = {{1 2 3 4 6} {5 3 8 1 2} {4 6 7 5 5} {2 4 8 9 4} }; Query1: tli = 0 tlj = 0 rbi = 1 rbj = 1 Query2: tli = 2 tlj = 2 rbi = 3 rbj = 4 Query3: tli = 1 tlj = 2 rbi = 3 rbj = 3; Output: Query1: 11 // Sum between (0 0) and (1 1) Query2: 38 // Sum between (2 2) and (3 4) Query3: 38 // Sum between (1 2) and (3 3)

Algoritm naiv:  

Putem bucla toate interogările și calcula fiecare interogare în O (q*(N*M)) cel mai rău caz, care este prea mare pentru o gamă largă de numere.

// Pseudo code of Naive algorithm. Arr[][] = input_matrix For each query: Input tli tlj rbi rbj sum = 0 for i from tli to tbi (inclusive): for j from tlj to rbj(inclusive): sum += Arr[i][j] print(sum) 

Soluție optimizată: 

Tabelul de suprafață însumat poate reduce acest tip de interogare în timpul de preprocesare de O(M*N) și fiecare interogare se va executa în O(1). Summed Area Table este o structură de date și un algoritm pentru generarea rapidă și eficientă a sumei valorilor dintr-un subset dreptunghiular al unei grile. 

Valoarea în orice punct (x y) din tabelul cu suprafețe însumate este doar suma tuturor valorilor de mai sus și din stânga lui (x y) inclusiv:

Soluția optimizată este implementată în postarea de mai jos.

  Implementarea abordării optimizate