Ņemot vērā M x N lieluma matricu, ir liels skaits vaicājumu, lai atrastu apakšmatricas summas. Vaicājumu ievades ir apakšmatricas kreisais augšējais un labais apakšējais indeksi, kuru summa ir jānoskaidro. 

Kā veikt matricas priekšapstrādi, lai apakšmatricas summu vaicājumus varētu veikt O(1) laikā. 

Piemērs:

  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)

Naivs algoritms:  

Mēs varam cilpot visus vaicājumus un aprēķināt katru vaicājumu O (q*(N*M)) sliktākajā gadījumā, kas ir pārāk liels lielam skaitļu diapazonam.

// 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) 

Optimizēts risinājums: 

Summētā platība tabula var samazināt šāda veida vaicājumu O(M*N) priekšapstrādes laikā, un katrs vaicājums tiks izpildīts O(1). Summētā apgabala tabula ir datu struktūra un algoritms, lai ātri un efektīvi ģenerētu vērtību summu režģa taisnstūrveida apakškopā. 

Vērtība jebkurā punktā (x y) summētās platības tabulā ir tikai visu vērtību summa, kas atrodas virs un pa kreisi no (x y), ieskaitot :

Optimizētais risinājums ir ieviests zemāk esošajā ziņojumā.

  Optimizētas pieejas ieviešana