2D Präfixsumme

Geschrieben von Benjamin Schmid.

In diesem Artikel schauen wir uns Präfixsummen an, zuerst im eindimensionalen Fall, dann in 2D. Dieser Trick ist leicht anwendbar, kann jedoch für viele Probleme als Baustein verwendet werden.

Problem

Was für Probleme können wir mit Präfixsumme lösen? Wir haben eine Tabelle mit Zahlen und wir müssen nun sehr oft die Summe in einem Teil der Tabelle berechnen. Oder etwas anders ausgedrückt: Es ist ein grosses \(M\times N\) Rechteck von Zahlen gegeben. Nun sollen für \(Q\) verschiedene Teilrechtecke die Summe aller Zahlen in diesem Teilrechteck berechnet werden.

Betrachten wir zunächst den eindimensionalen Fall, bei dem man eine Liste mit \(N\) Zahlen hat. Unser erster Ansatz ist, für jeden gefragten Bereich die einzelnen Zahlen zu addieren. Also etwas in der Art:

for segment in segments: # Q Abfragen
  sum = 0
  for i in range(segment.start, segment.end):
    sum += list_of_numbers[i]
  print(sum)

Dies ist jedoch für viele Anfragen zu langsam, da jede der \(Q\) Abfragen bis zu \(N\) Operationen benötigt. Der Algorithmus läuft also in \(\mathcal{O}(N\cdot Q)\).

Lösung

Der Trick ist nun, zu Beginn etwas mehr zu rechnen und einige Werte vorzuberechnen. Mit diesen zusätzlichen Informationen können wir die einzelnen Abfragen schneller beantworten. Statt für jede Abfrage alle Zahlen in \(\mathcal{O}(N)\) aufzusummieren, können wir danach die Summe in \(\mathcal{O}(1)\) berechnen. Schauen wir uns nun an, wie dies funktioniert.

Die Liste \(A\) mit den Elementen \(a_1\), \(a_2\), \(a_3\), …, \(a_N\) enthält die Zahlen aus der Eingabe. Um die Summe im Bereich \(x\) bis \(y\) zu berechnen, können wir auch alle Zahlen von Anfang bis \(y\) aufsummieren, und dann alle Zahlen von Anfang bis \(x-1\) wieder abziehen. Wenn wir nun mehrere Bereiche haben, die alle bei \(y\) enden, ändert sich die erste Summe (von Anfang bis \(y\)) nicht. Nur diejenige, die wir wieder abziehen (Anfang bis \(x-1\)), ändert sich. Dies gilt ähnlich, wenn sich \(x\) nicht ändert und nur \(y\). Das sieht doch sehr gut aus, um da etwas vorauszuberechnen!

Wir werden also zu Beginn eine Liste \(B\) vorberechnen, so dass \(b_i\) gerade der Summe aller Zahlen der Liste \(A\) bis und mit \(i\) entspricht. Nun können wir die oben vorgeschlagene Methode verwenden: die Summe im Bereich \(x\) bis \(y\) ist genau \(b_y - b_{x-1}\). Warum funktioniert das?

Schauen wir uns z.B. den Bereich \(3 - 6\) an. Die Summe die wir berechnen wollen ist also \(a_3 + a_4 + a_5 + a_6\). Dann ist \(b_6 = a_1 + a_2 + a_3 + a_4 + a_5 + a_6\) und \(b_2 = a_1 + a_2\). Rechnen wir nun \(b_6 - b_2\), so ergibt dies \(b_6 - b_2 =\) \((a_1 + a_2 + a_3 + a_4 + a_5 + a_6) - (a_1 + a_2) =\) \((a_1 - a_1) + (a_2 - a_2) + a_3 + a_4 + a_5 + a_6 =\) \(a_3 + a_4 + a_5 + a_6\). Dies ist genau die Summe, die wir suchen. Wir können also durch die Subtraktion die zu viel hinzuaddierten Elemente wieder “entfernen”.

Implementieren kann man das z.B. folgendermassen:

# vorberechnen
b = [0] * len(a)
b[0] = a[0]
for i in range(1, len(a)):
  b[i] = b[i-1] + a[i]

# Abfragen
for segment in segments:
  if segment.start == 0:
    print(b[segment.end])
  else:
    print(b[segment.end] - b[segment.start-1])

Das Vorberechnen können wir in \(\mathcal{O}(N)\) erledigen und alle Abfragen in \(\mathcal{O}(Q)\) (da jede Abfrage in konstanter Zeit beantwortet werden kann). Somit verbessert sich unsere Lösung von \(\mathcal{O}(N\cdot Q)\) auf \(\mathcal{O}(N+Q)\).

Lösung für zwei Dimensionen

Diese Idee kann auch auf den zweidimensionalen Fall erweitert werden.

Sei \(A\) das gegebene Rechteck mit Zahlen und \(B\) unser vorberechnetes Rechteck. Welche Werte benötigen wir in \(B\), um die Summe von Teilrechtecken effizient zu berechnen? Wie wir in der Grafik oben sehen, lässt sich das gelbe Rechteck aus den vier anderen Rechtecken berechnen (diese stellen jeweils die Summe der abgedeckten Felder dar). Diese vier Recktecke haben ihre linken oberen Ecken in der linken oberen Ecke von \(A\). Dies ist genau wie im eindimensionalen Fall, wo alle Bereiche bis an das linke Ende reichten.

Wir berechnen in \(B\) also jeweils die Summe des Teilrechtecks von der linken oberen Ecke bis zum aktuellen Feld. Dies kann man auf verschiedene Arten effizient berechnen. Eine Möglichkeit ist, das Rechteck von oben links durchzugehen und jeweils \(b_{y,x} = b_{y-1,x} + b_{y,x-1} - b_{y-1,x-1} + a_{y,x}\) zu setzen. Die Subtraktion wird benötigt, da wir sonst dieses Teilrechteck doppelt zählen würden.

Nun kann die Summe des Teilrechtecks von \((i_x|i_y)\) bis \((j_x|j_y)\) ausgerechnet werden mit \(b_{j_y,j_x} - b_{i_y-1,j_x} - b_{j_y,i_x-1} + b_{i_y-1,i_x-1}\). Wir nehmen also wieder den zu grossen Bereich, der bis \((j_x|j_y)\) geht. Anschliessend ziehen wir den linken Bereich sowie den oberen Bereich ab, den wir zu viel hinzugezählt haben. Nun haben wir den Bereich bis \((i_x-1|i_y-1)\) jedoch zweimal abgezogen, weshalb wir ihn wieder hinzuaddieren. Beachte, dass für die Berechnung und Abfrage verschiedene Formeln verwendet werden.

Den Algorithmus kann man nun folgendermassen implementieren:

# vorberechnen
b = [[0] * (width + 1)] * (height + 1)
for y in range(1, height):
  for x in range(1, width):
    b[y][x] = b[y-1][x] + b[y][x-1] - b[y-1][x-1] + a[y-1][x-1]

# Abfragen
for segment in segments:
  print(b[segment.y2][segment.x2]
        - b[segment.y1][segment.x2]
        - b[segment.y2][segment.x1]
        + b[segment.y1][segment.x1])

Beispielaufgabe

Schauen wir uns zum Schluss eine Aufgabe an, die man damit lösen kann.

Um einen genaueren Wetterbericht zu erstellen, werden regelmässig Temperaturen gemessen. Über die Karte wird dazu ein Gitter gelegt und in jedes Feld die Temperatur an diesem Ort geschrieben. Für den Wetterbericht werden die Durchschnittstemperaturen vieler verschiedenen, rechteckigen Teilgebieten benötigt.

Wir könnten für jede Frage nach der Durchschnittstemperatur alle Werte in dieser Region aufsummieren und durch die Anzahl Felder teilen. Doch wir haben soeben einen besseren Ansatz kennen gelernt: wir berechnen die Präfixsummen vor und können so die Abfragen in konstanter Zeit beantworten (d.h. unabhängig davon, wie gross die Region bzw. die gesamte Karte ist).

Oft kommen Präfixsummen etwas versteckt in einer Aufgabe vor und sind nur ein Baustein für den kompletten Algorithmus. Deshalb ist es sehr hilfreich, diesen beim Lösen von Aufgaben im Hinterkopf zu behalten.