Data una matrice di dimensione M x N, è necessario eseguire un gran numero di query per trovare le somme delle sottomatrici. Gli input per le query sono gli indici in alto a sinistra e in basso a destra della sottomatrice la cui somma è da scoprire. 

Come preelaborare la matrice in modo che le query sulla somma delle sottomatrici possano essere eseguite in tempo O(1). 

Esempio:

  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)

Algoritmo ingenuo:  

Possiamo eseguire un loop di tutte le query e calcolare ciascuna query nel caso peggiore O (q*(N*M)), che è troppo grande per un ampio intervallo di numeri.

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

Soluzione ottimizzata: 

Tabella delle aree sommate può ridurre questo tipo di query in un tempo di preelaborazione di O(M*N) e ogni query verrà eseguita in O(1). La tabella dell'area sommata è una struttura dati e un algoritmo per generare in modo rapido ed efficiente la somma dei valori in un sottoinsieme rettangolare di una griglia. 

Il valore in qualsiasi punto (x y) nella tabella dell'area sommata è solo la somma di tutti i valori sopra e a sinistra di (x y) compreso:

La soluzione ottimizzata è implementata nel post seguente.

  Implementazione di un approccio ottimizzato