Donada una matriu de mida M x N, hi ha un gran nombre de consultes per trobar sumes de submatrius. Les entrades a les consultes són índexs superior esquerre i inferior dret de la submatriu la suma de la qual és esbrinar. 

Com preprocessar la matriu perquè les consultes de suma de submatrius es puguin realitzar en temps O(1). 

Exemple:

  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)

Algorisme ingenu:  

Podem recórrer totes les consultes i calcular cada consulta en el pitjor cas O (q*(N*M)), que és massa gran per a una àmplia gamma de números.

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

Solució optimitzada: 

Taula d'àrea sumada pot reduir aquest tipus de consulta al temps de preprocessament de O(M*N) i cada consulta s'executarà en O(1). Summed Area Table és una estructura de dades i un algorisme per generar de manera ràpida i eficient la suma de valors en un subconjunt rectangular d'una quadrícula. 

El valor en qualsevol punt (x y) de la taula d'àrea sumada és només la suma de tots els valors de dalt i a l'esquerra de (x y) inclòs:

La solució optimitzada s'implementa a la següent publicació.

  Implementació de l'enfocament optimitzat