Als Präfixsumme einer Zahlenfolge bezeichnet man die schrittweise Addition der einzelnen Zahlen. Dabei wird jede Zahl zur vorhergehenden Summe addiert.
Wir können die Berechnung allgemein folgendermaßen darstellen: si = si-1 + xi
Um diese Definition zu verdeutlichen, berechnen wir für zufällig gewählte Zahlen die Präfixsumme:
| Zahlen | 3 | 7 | 12 | 4 | -6 | 2 | -4 |
|---|---|---|---|---|---|---|---|
| Präfixsumme | 3 | 10 | 22 | 26 | 20 | 22 | 18 |
Noch einmal der Rechenvorgang aufgelistet:
| Index (i) | Zahl (x) | Berechnung | Summe (s) |
|---|---|---|---|
| 1 | 3 | 0 + 3 | 3 |
| 2 | 7 | 3 + 7 | 10 |
| 3 | 12 | 10 + 12 | 22 |
| 4 | 4 | 22 + 4 | 26 |
| 5 | -6 | 26 - 6 | 20 |
| 6 | 2 | 20 + 2 | 22 |
| 7 | -4 | 22 - 4 | 18 |
Jetzt wissen wir was die Präfixsumme ist und wie wir sie berechnen. Sehen wir uns nun ein paar Beispiele an, die wir über diese Berechnung lösen bzw. optimieren können: