Segmentbaum: Aufbau und Abfragen
Ermitteln Sie Bereichsminimum, -maximum oder -summe in log n
Segmentbaum: Aufbau und Abfragen ist eine kostenlose Coding Interview Prep-Lektion auf CoddyKit. Dies ist Lektion 3 von 4. Du kannst die komplette Lektion unten kostenlos lesen – dann übst du sie direkt im Browser mit einem integrierten Code-Editor und einem KI-Tutor rund um die Uhr. Sie ist Teil des Coding Interview Prep-Lernpfads, und dein Fortschritt wird über Web und CoddyKit-App synchronisiert. Der Coding Interview Prep-Kurs umfasst insgesamt 4 Lektionen.
Über den Fenwick-Baum hinaus
Ein Fenwick-Baum ist hervorragend für Summen geeignet, aber ein Segmentbaum verarbeitet auch Minimum, Maximum, GGT und mehr. Er ist das flexible Arbeitstier für Bereichsabfragen.
Ein Baum über Bereichen
Jeder Knoten besitzt einen Bereich des Arrays. Die Wurzel deckt alles ab; die Kindknoten teilen den Bereich immer weiter in zwei Hälften, bis die Blätter einzelne Elemente enthalten.
Speicherung in einem Array
Wir speichern den Baum in einem flachen Array der Größe 2n oder 4n. Knoten 1 ist die Wurzel; die Kinder von Knoten i befinden sich bei 2i und 2i+1.
seg = [0] * (2 * n)Blätter enthalten die Daten
In der iterativen Variante liegen die ursprünglichen Werte in der zweiten Hälfte des Arrays, an den Indizes n bis 2n-1.
for i in range(n):
seg[n + i] = a[i]Von unten nach oben aufbauen
Jeder innere Knoten ist das combine seiner beiden Kinder. Füllen Sie die Knoten von n-1 abwärts bis 1, dann ist der gesamte Baum fertig.
for i in range(n - 1, 0, -1):
seg[i] = seg[2*i] + seg[2*i+1]Die Combine-Operation
Die Funktion combine definiert den Baum. Verwenden Sie plus für Summen, min für Minima oder max für Maxima. Tauschen Sie sie aus, um die Abfrage zu ändern.
def combine(x, y):
return min(x, y)Punkt-Update und anschließend aufsteigen
Um einen Wert zu ändern, setzen Sie das Blatt und gehen Sie zur Wurzel hinauf. Dabei berechnen Sie jeden Elternknoten aus seinen beiden Kindern neu.
i += n
seg[i] = value
while i > 1:
i //= 2
seg[i] = combine(seg[2*i], seg[2*i+1])Einen halboffenen Bereich abfragen
Bereichsabfragen durchlaufen den Bereich von beiden Enden aus und verbinden die Randknoten mit dem Ergebnis. Das Intervall ist halboffen und umfasst l bis einschließlich vor r.
Die iterative Abfrageschleife
Bewegen Sie l und r aufeinander zu. Wenn ein Index eine ungerade Grenze bildet, nehmen Sie den entsprechenden Knoten auf, bevor Sie den Zeiger weiterbewegen.
while l < r:
if l & 1: res = combine(res, seg[l]); l += 1
if r & 1: r -= 1; res = combine(res, seg[r])
l //= 2; r //= 2An beiden Enden logarithmisch
Der Aufbau benötigt O(n), während jedes Update und jede Abfrage O(log n) benötigt. Dieses Verhältnis macht Segmentbäume so vielseitig.
Beachten Sie das neutrale Element
Beginnen Sie Ihr Ergebnis mit dem neutralen Element der Operation: 0 für Summen, unendlich für Minima und minus unendlich für Maxima. Ein falscher Anfang liefert falsche Ergebnisse.
res = float('inf')Kurztest
Wo befinden sich die ursprünglichen Daten im iterativen Baum?
Zusammenfassung: Flexible Bereiche
Sie haben einen Segmentbaum erstellt: Blätter in der zweiten Hälfte, Elternknoten als combines und O(log n) für Updates und Abfragen von Summen, Minima oder Maxima. 🌳
Häufig gestellte Fragen
Ist die Lektion „Segmentbaum: Aufbau und Abfragen“ kostenlos?
Ja — der vollständige Text von „Segmentbaum: Aufbau und Abfragen“ ist hier im Web kostenlos zu lesen. Um sie interaktiv zu üben (integrierter Code-Editor und 24/7 KI-Tutor) und den Rest des Coding Interview Prep-Kurses freizuschalten, upgrade auf CoddyKit PRO. Der Coding Interview Prep-Kurs umfasst insgesamt 4 Lektionen.
Was lerne ich in „Segmentbaum: Aufbau und Abfragen“?
Ermitteln Sie Bereichsminimum, -maximum oder -summe in log n Du übst Coding Interview Prep mit praktischem Code, den du direkt im Browser ausführst, und ein 24/7 KI-Tutor beantwortet deine Fragen während du die Lektion bearbeitest.
Brauche ich Erfahrung, um Coding Interview Prep zu starten?
Keine Vorkenntnisse erforderlich. Coding Interview Prep auf CoddyKit ist für Anfänger bis fortgeschrittene Lernende strukturiert, sodass du hier starten oder von Anfang an beginnen und in deinem eigenen Tempo voranschreiten kannst. Dies ist Lektion 3 von 4.
Wie lange dauert die Lektion „Segmentbaum: Aufbau und Abfragen“?
Die meisten CoddyKit-Lektionen dauern etwa 5–10 Minuten. Jede ist kompakt und interaktiv, sodass du stetig Fortschritte machst und genau dort weitermachst, wo du aufgehört hast – im Web und in der App.
Kann ich in dieser Coding Interview Prep-Lektion Code schreiben und ausführen?
Ja. Jede Coding Interview Prep-Lektion enthält einen integrierten Code-Editor, sodass du echten Code direkt in deinem Browser schreibst und ausführst und sofort KI-Feedback erhältst — ohne lokale Einrichtung erforderlich.
Alle Lektionen in diesem Kurs
- Fenwick-Baum für Präfixsummen
- Inversionen mit einem BIT
- Segmentbaum: Aufbau und Abfragen
- Lazy Propagation für Bereichsaktualisierungen