Veröffentlicht · wird verbessert
Algorithm
Ein Segmentbaum beantwortet Bereichsabfragen wie Summe oder Minimum und ändert Werte in O(log n); der Fenwick-Baum ist die schlanke Variante für Summen.
Ein Segmentbaum ist ein Binärbaum, der für jeden Bereich, der durch wiederholtes Halbieren eines Arrays entsteht, eine Zusammenfassung wie Summe, Minimum oder Maximum speichert. Die Wurzel deckt das ganze Array ab, jedes Blatt ein einzelnes Element, und jeder innere Knoten kombiniert seine beiden Kinder. So lässt sich jede Frage zu einem zusammenhängenden Bereich aus wenigen Knoten beantworten.
Präfixsummen liefern Bereichssummen in O(1), brauchen aber O(n) für eine einzige Änderung; ein unverändertes Array ist schnell beim Ändern, aber langsam bei jeder Abfrage. Ein Segmentbaum erledigt Punktänderungen und Bereichsabfragen beide in O(log n) und passt deshalb überall dort, wo sich Werte ständig ändern und laufend Bereichsfragen eintreffen. Mit Lazy Propagation unterstützt er zusätzlich Bereichsänderungen, etwa das Addieren eines Werts zu einem ganzen Bereich, in O(log n).
Am besten versteht man zuerst, wo Präfixsummen an ihre Grenzen stoßen, zeichnet dann einen kleinen Baum von Hand und verfolgt, welche Knoten eine Abfrage und eine Änderung berühren. Danach schreibt man die kurze iterative Implementierung und einen Fenwick-Baum selbst und übt an klassischen Aufgaben wie Bereichsminimum, Inversionen zählen und Bereichsaddition mit Bereichssumme.
Jeder Knoten ist für einen Bereich des Arrays zuständig und speichert dessen Summe oder Minimum; jede assoziative Operation mit neutralem Element passt in dieselbe Struktur.
Eine Elementänderung berechnet nur einen Pfad vom Blatt zur Wurzel neu, und eine Bereichsabfrage kombiniert höchstens zwei Knoten pro Ebene.
Eine Bereichsänderung hinterlässt eine Notiz an den abdeckenden Knoten und gibt sie erst an die Kinder weiter, wenn eine Operation tiefer steigen muss.
Für umkehrbare Operationen wie Summen erreicht ein Fenwick-Baum (BIT) dieselbe Komplexität mit einem Array der Länge n + 1 und wenigen kurzen Schleifen.
Ein iterativer Segmentbaum: Die Elemente liegen in der zweiten Hälfte eines Arrays der Länge 2n, und jeder vordere Platz hält die Summe seiner beiden Kinder. update steigt vom Blatt zur Wurzel und berechnet die Summen neu, query steigt von beiden Enden des halboffenen Bereichs [left, right) auf und addiert nur die Randknoten. Die Ausgabe lautet 26, 17 und 28.
segment_tree.py
class SegmentTree:
"""Iterative segment tree: point update and range sum in O(log n)."""
def __init__(self, values):
self.n = len(values)
self.tree = [0] * self.n + list(values)
for i in range(self.n - 1, 0, -1):
self.tree[i] = self.tree[2 * i] + self.tree[2 * i + 1]
def update(self, index, value):
i = index + self.n
self.tree[i] = value
while i > 1:
i //= 2
self.tree[i] = self.tree[2 * i] + self.tree[2 * i + 1]
def query(self, left, right):
"""Sum of values[left:right] (half-open range)."""
total = 0
lo, hi = left + self.n, right + self.n
while lo < hi:
if lo & 1:
total += self.tree[lo]
lo += 1
if hi & 1:
hi -= 1
total += self.tree[hi]
lo //= 2
hi //= 2
return total
if __name__ == "__main__":
tree = SegmentTree([5, 3, 7, 9, 6, 4, 1, 2])
print(tree.query(2, 6)) # 7 + 9 + 6 + 4 = 26
tree.update(3, 0)
print(tree.query(2, 6)) # 7 + 0 + 6 + 4 = 17
print(tree.query(0, 8)) # 28
python segment_tree.pySechs Kapitel führen dich von der Installation bis zu den Kernkonzepten von Segmentbäume.
Stelle Fragen, teile Erfahrungen und tausche Meinungen zu Segmentbäume aus.
Noch keine Diskussionen. Starte die erste.
0 Kommentare
Anmelden · Melde dich an, um einen Kommentar zu schreiben.
Schreib den ersten Kommentar.