====== Präfixsumme ======
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: **s<sub>i</sub> = s<sub>i-1</sub> + x<sub>i</sub>**

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:

  * [[algo:prefix-sum:optimization:stocks|Summierung von Aktienpositionen]]
  * [[algo:prefix-sum:optimization:area|Größtmögliche freie Grundstücksfläche]]

===== Siehe auch =====
  * [[https://www.proggen.org/forum/viewtopic.php?f=39&t=7636|Autorendiskussion]]
  * [[algo:knapsack|Rucksackproblem]]
  * [[struct:tree:fenwick|Binary Indexed Tree (Fenwick Tree)]]