Algorithmen und Datenstrukturen · Junior · Frage 67 von 75
Was ist ein Präfixsummen-Array?
- 1Ein Array der ersten Zeichen jedes Strings
- 2Element
iist die Summe der ersteniElemente - 3Das ursprüngliche Array, einmal aufsteigend sortiert
Antwort zeigen
Richtige Antwort: Element i ist die Summe der ersten i Elemente
Erklärung
Nach einem O(n)-Durchlauf ist die Summe jedes Bereichs [l, r) in O(1) prefix[r] - prefix[l]. Das ist der Standardtrick, wenn man dasselbe Array nach vielen Bereichssummen fragt.