Lazy Propagation für Bereichsaktualisierungen
Stellen Sie Aktualisierungen für ganze Bereiche zurück
Lazy Propagation für Bereichsaktualisierungen ist eine kostenlose Coding Interview Prep-Lektion auf CoddyKit. Dies ist Lektion 4 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.
Das Problem der Bereichsaktualisierung
Was ist, wenn eine Abfrage verlangt, zu jedem Element von l bis r 5 zu addieren? Jedes Blatt einzeln zu bearbeiten benötigt O(n) pro Update – bei vielen Bereichsaktualisierungen viel zu langsam. 😰
Die Lazy-Idee
Lazy Propagation ermöglicht es einem Knoten, eine ausstehende Änderung zu speichern, ohne sie sofort an seine Kinder weiterzugeben. Die Arbeit wird aufgeschoben, bis Sie diese Kinder tatsächlich benötigen.
Ein zweites Array für ausstehende Arbeit
Zusätzlich zum Baum führen wir ein lazy-Array. lazy[node] speichert ein Update, das auf den gesamten Bereich dieses Knotens angewendet wird, aber noch nicht nach unten weitergegeben wurde.
lazy = [0] * (4 * n)Auf einen ganzen Knoten anwenden
Wenn ein Update einen Knoten vollständig abdeckt, passen Sie seinen gespeicherten Wert an und legen Sie die Änderung in lazy ab. Danach können Sie stoppen. Ein Abstieg ist nicht nötig.
seg[node] += (r - l + 1) * val
lazy[node] += valVor dem Abstieg nach unten weitergeben
Bevor Sie die Kinder besuchen, geben Sie jeden ausstehenden Lazy-Wert an beide Kinder weiter. So sind die Kinder genau dann korrekt, wenn Sie sie auslesen.
def push_down(node, l, r):
if lazy[node]:
apply(2*node, l, mid)
apply(2*node+1, mid+1, r)
lazy[node] = 0Drei Fälle pro Knoten
Am jeweiligen Knoten ist der Abfragebereich disjunkt, deckt ihn vollständig ab oder überschneidet sich teilweise mit ihm. Überspringen Sie ihn, wenden Sie die Änderung verzögert an oder steigen Sie jeweils in beide Hälften ab.
Lazy-Updates bleiben logarithmisch
Eine Bereichsaktualisierung berührt nur O(log n) Knoten, weil Knoten mit vollständiger Abdeckung frühzeitig stoppen. Das ist der gesamte Vorteil des Lazy-Ansatzes. ⚡
Abfragen ebenfalls nach unten weitergeben
Bereichsabfragen müssen vor dem Rekursionsschritt ebenfalls nach unten weitergegeben werden, damit sie aktuelle Werte der Kindknoten lesen. Das zu vergessen ist der klassische Fehler bei Lazy Propagation.
Nach der Rekursion nach oben übernehmen
Nach dem Aktualisieren der Kindknoten setzen Sie den Elternknoten aus ihnen neu zusammen. Dieses Übernehmen nach oben hält jeden inneren Knoten mit seinem Teilbaum konsistent.
seg[node] = seg[2*node] + seg[2*node+1]Zuweisung und Addition
Lazy Propagation funktioniert für viele Operationen, aber Zuweisung und Addition werden unterschiedlich kombiniert. Legen Sie fest, wie zwei ausstehende Aktualisierungen zusammengeführt werden, bevor Sie den Code schreiben.
Wann sich Lazy Propagation lohnt
Verwenden Sie Lazy Propagation nur, wenn Sie tatsächlich Bereichsaktualisierungen benötigen. Für reine Punktaktualisierungen ist ein einfacher Segmentbaum übersichtlicher und ausreichend.
Schnelltest
Was muss geschehen, bevor Sie zu den Kindknoten eines Knotens rekursiv hinabsteigen?
Rückblick: Aufgeschobene Aktualisierungen
Sie haben Lazy Propagation kennengelernt: ausstehende Änderungen speichern, vor dem Abstieg nach unten weitergeben, danach nach oben übernehmen und Bereichsaktualisierungen in O(log n) ausführen. 🎉
Häufig gestellte Fragen
Ist die Lektion „Lazy Propagation für Bereichsaktualisierungen“ kostenlos?
Ja — der vollständige Text von „Lazy Propagation für Bereichsaktualisierungen“ 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 „Lazy Propagation für Bereichsaktualisierungen“?
Stellen Sie Aktualisierungen für ganze Bereiche zurück 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 4 von 4.
Wie lange dauert die Lektion „Lazy Propagation für Bereichsaktualisierungen“?
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