Givet en matrix af størrelsen M x N er der et stort antal forespørgsler for at finde submatrix-summer. Input til forespørgsler er venstre øverste og højre nederste indekser af submatrix, hvis sum er at finde ud af. 

Hvordan man forbehandler matrixen, så submatrix sum forespørgsler kan udføres på O(1) tid. 

Eksempel:

  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 algoritme:  

Vi kan sløjfe alle forespørgslerne og beregne hver forespørgsel i O (q*(N*M)) worst case, hvilket er for stort til et stort antal tal.

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

Optimeret løsning: 

Opsummeret arealtabel kan reducere denne type forespørgsel til forbehandlingstid på O(M*N), og hver forespørgsel udføres i O(1). Summed Area Table er en datastruktur og algoritme til hurtigt og effektivt at generere summen af ​​værdier i en rektangulær delmængde af et gitter. 

Værdien på ethvert punkt (x y) i den summerede arealtabel er kun summen af ​​alle værdierne over og til venstre for (x y) inklusive:

Den optimerede løsning er implementeret i nedenstående indlæg.

  Implementering af optimeret tilgang