Adott egy M x N méretű mátrix, nagyszámú lekérdezés van az almátrix összegeinek megtalálásához. A lekérdezések bemenetei az almátrix bal felső és jobb alsó indexei, amelyek összegét kell kideríteni. 

A mátrix előfeldolgozása úgy, hogy a részmátrix összegének lekérdezése O(1) idő alatt végrehajtható legyen. 

Példa:

  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)

Naiv algoritmus:  

Az összes lekérdezést hurkolhatjuk, és minden lekérdezést kiszámolhatunk O (q*(N*M)) legrosszabb esettel, ami túl nagy egy nagy számtartományhoz.

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

Optimalizált megoldás: 

Összesített terület táblázat Az ilyen típusú lekérdezéseket az O(M*N) előfeldolgozási idejére csökkentheti, és minden lekérdezés O(1)-ben fog végrehajtódni. A Summed Area Table egy adatstruktúra és algoritmus az értékek összegének gyors és hatékony generálására egy rács téglalap alakú részhalmazában. 

Az összegzett területtáblázat bármely pontjában (x y) lévő érték csak az (x y) feletti és attól balra lévő értékek összege, beleértve :

Az optimalizált megoldást az alábbi bejegyzésben valósítjuk meg.

  Optimalizált megközelítés megvalósítása