Atsižvelgiant į M x N dydžio matricą, yra daug užklausų norint rasti submatricos sumas. Užklausų įvestis yra kairysis viršutinis ir dešinysis apatinis submatricos indeksai, kurių sumą reikia išsiaiškinti. 

Kaip iš anksto apdoroti matricą, kad submatricos sumos užklausas būtų galima atlikti per O(1) laiką. 

Pavyzdys:

  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)

Naivus algoritmas:  

Galime atlikti visas užklausas ir apskaičiuoti kiekvieną užklausą O (q*(N*M)) blogiausiu atveju, kuris yra per didelis dideliam skaičių diapazonui.

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

Optimizuotas sprendimas: 

Suminė ploto lentelė gali sumažinti šio tipo užklausą į išankstinio apdorojimo laiką O(M*N) ir kiekviena užklausa bus vykdoma O(1). Sumuotų plotų lentelė yra duomenų struktūra ir algoritmas, skirtas greitai ir efektyviai generuoti verčių sumą stačiakampiame tinklelio poaibyje. 

Vertė bet kuriame suminės ploto lentelės taške (x y) yra tik visų aukščiau ir kairėje nuo (x y) esančių verčių suma, įskaitant:

Optimizuotas sprendimas įgyvendintas žemiau esančiame įraše.

  Optimizuoto požiūrio įgyvendinimas