Gegeven een matrix met de grootte M x N zijn er een groot aantal zoekopdrachten om submatrixsommen te vinden. Invoer voor zoekopdrachten bestaat uit indexen linksboven en rechtsonder van de submatrix waarvan de som moet worden uitgezocht. 

Hoe de matrix voor te verwerken, zodat submatrixsomquery's in O(1) tijd kunnen worden uitgevoerd. 

Voorbeeld:

  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) 

Naïef algoritme:  

We kunnen alle zoekopdrachten herhalen en elke zoekopdracht berekenen in het ergste geval O (q*(N*M)), wat te groot is voor een groot bereik aan getallen.

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

Geoptimaliseerde oplossing: 

Tabel met opgetelde gebieden kan dit type query reduceren tot een voorverwerkingstijd van O(M*N) en elke query wordt uitgevoerd in O(1). Summed Area Table is een datastructuur en algoritme voor het snel en efficiënt genereren van de som van waarden in een rechthoekige subset van een raster. 

De waarde op elk punt (xy) in de tabel met opgetelde gebieden is slechts de som van alle waarden hierboven en links van (xy) inclusief:

De geoptimaliseerde oplossing is geïmplementeerd in het onderstaande bericht.

  Implementatie van een geoptimaliseerde aanpak