Algorithmen und Datenstrukturen · Senior · Frage 8 von 75
Wann wählt man einen Segmentbaum statt eines Fenwick-Baums?
- 1Für Bereichsabfragen wie Minimum oder Maximum oder für Bereichs-Updates
- 2Wenn sich das Array nach dem Erzeugen nie ändert
- 3Wenn der Speicher strikt unter n Elementen bleiben muss
Antwort zeigen
Richtige Antwort: Für Bereichsabfragen wie Minimum oder Maximum oder für Bereichs-Updates
Erklärung
Fenwick-Bäume passen zu invertierbaren Operationen wie Summen. Ein Segmentbaum speichert ein Aggregat pro Segment und unterstützt jede assoziative Operation (min, max, ggT) sowie mit Lazy Propagation Bereichs-Updates. Er nutzt etwa 2n bis 4n Knoten.