Bei einer gegebenen Matrix der Größe M x N gibt es eine große Anzahl von Abfragen, um Submatrixsummen zu finden. Eingaben für Abfragen sind die Indizes links oben und rechts unten der Submatrix, deren Summe ermittelt werden soll. 

So verarbeiten Sie die Matrix vor, sodass Submatrix-Summenabfragen in O(1)-Zeit durchgeführt werden können. 

Beispiel:

  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)

Naiver Algorithmus:  

Wir können alle Abfragen schleifen und jede Abfrage im schlimmsten Fall O (q*(N*M)) berechnen, der für einen großen Zahlenbereich zu groß ist.

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

Optimierte Lösung: 

Tabelle der summierten Fläche kann diese Art von Abfrage auf die Vorverarbeitungszeit von O(M*N) reduzieren und jede Abfrage wird in O(1) ausgeführt. Die Summed Area Table ist eine Datenstruktur und ein Algorithmus zur schnellen und effizienten Generierung der Summe von Werten in einer rechteckigen Teilmenge eines Rasters. 

Der Wert an jedem Punkt (x y) in der summierten Flächentabelle ist einfach die Summe aller Werte über und links von (x y) einschließlich:

Die optimierte Lösung wird im folgenden Beitrag implementiert.

  Implementierung eines optimierten Ansatzes