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: