Givet en matris med storleken M x N finns det ett stort antal frågor för att hitta submatrissummor. Indata till frågor är vänster övre och höger nedre index av submatris vars summa är att ta reda på. 

Hur man förbearbetar matrisen så att submatrissummafrågor kan utföras i O(1) tid. 

Exempel:

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

Vi kan loopa alla frågor och beräkna varje fråga i O (q*(N*M)) värsta fall som är för stort för ett stort antal siffror.

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

Optimerad lösning: 

Sammansatt områdestabell kan reducera denna typ av fråga till förbearbetningstid för O(M*N) och varje fråga kommer att köras i O(1). Summed Area Table är en datastruktur och algoritm för att snabbt och effektivt generera summan av värden i en rektangulär delmängd av ett rutnät. 

Värdet vid valfri punkt (x y) i den summerade areatabellen är bara summan av alla värden ovanför och till vänster om (x y) inklusive:

Den optimerade lösningen implementeras i nedanstående inlägg.

  Implementering av optimerat tillvägagångssätt