Algorithmen und Datenstrukturen · Senior · Frage 7 von 75
Welches Problem löst ein Fenwick-Baum (Binary Indexed Tree)?
- 1Ein Array an Ort und Stelle in O(n) Zeit sortieren
- 2Kürzeste Wege in einer gewichteten Baumstruktur
- 3Präfixsummen mit Updates, beides in O(log n)
Antwort zeigen
Richtige Antwort: Präfixsummen mit Updates, beides in O(log n)
Erklärung
Einfache Präfixsummen machen Abfragen O(1), Updates aber O(n). Ein Fenwick-Baum bringt beide auf O(log n) und springt über das niedrigste gesetzte Bit des Index (i & -i) zwischen Bereichen.