Overview
Ein Segment-Baum beantwortet Bereichsabfragen (Summe, Min, Max) und Aktualisierungen in O(log n).
Analogy
Unternehmenshierarchie: jeder Manager speichert das Aggregat (Summe/Max/Min) seines gesamten Teams.
Step-by-step
- Aufbau: O(n) – jeder Knoten speichert Aggregat seines Bereichs.
- Bereichsabfrage [l,r]: rekursiv absteigen, Segmente kombinieren die in [l,r] passen.
- Punktaktualisierung: O(log n) – Blatt aktualisieren, Vorfahren neu berechnen.
- Bereichsaktualisierung mit Lazy-Propagation: Aktualisierungen aufschieben, bei Bedarf anwenden.
Visual
Knoten für [0,7] deckt alle 8 Elemente ab; Knoten für [0,3] linke Hälfte; Blatt [2,2] deckt arr[2] ab.
Common mistakes
- Off-by-One in Bereichsgrenzen (inklusiv vs. exklusiv).
- Lazy-Tags vor Kinder-Abfrage vergessen zu propagieren.
Practice questions
- Summen-Segment-Baum aufbauen; Summe von [l,r] abfragen.
- Lazy Bereichs-Addition-Aktualisierung hinzufügen.
Time
O(n) Aufbau, O(log n) Abfrage/Aktualisierung