Differenz-Arrays für Bereichsaktualisierungen

Präfixsummen beantworten Bereichsabfragen schnell. Ein Differenzarray kehrt das Prinzip um und wendet viele Bereichsaktualisierungen schnell an. 🔁

Wenn Sie bei vielen Wiederholungen jedem Element eines Bereichs einen Wert hinzufügen, kostet jede Aktualisierung O(n). Über q Aktualisierungen hinweg explodiert dieser Aufwand.

Statt jede Zelle anzufassen, speichern Sie nur, wo eine Änderung beginnt und wo sie endet. Markieren Sie die Ränder, nicht die Mitte.

Ein Differenzarray speichert die Differenz zwischen jedem Element und dem vorherigen. Wenn Sie eine solche Differenz ändern, verschieben Sie damit einen ganzen späteren Abschnitt.

Um v auf den Bereich von l bis r zu addieren, addieren Sie v am Index l und subtrahieren v am Index r + 1. Nur zwei Änderungen decken den gesamten Bereich ab.

Das Plus bei l schaltet die Änderung ein, das Minus bei r + 1 schaltet sie wieder aus. Zusammen begrenzen sie die Aktualisierung auf einen Bereich.

Jede Aktualisierung besteht nur aus zwei Array-Schreibzugriffen, daher benötigen q Aktualisierungen insgesamt O(q). Die aufwendige Arbeit wird bis zum Ende aufgeschoben.

Nachdem alle Markierungen gesetzt sind, berechnen Sie eine Präfixsumme des Differenzarrays. Dieser eine Durchlauf rekonstruiert jeden endgültigen Wert.

Machen Sie das Array um eine Zelle länger, damit r + 1 niemals über das Ende hinausgeht. Dieser zusätzliche Schutzplatz verhindert Indexfehler.

Sie benötigen O(q), um die Aktualisierungen zu markieren, und einen Durchlauf mit O(n), um das Array wiederherzustellen. Der kombinierte Aufwand liegt weit unter dem naiven O(n mal q).

Differenzarrays eignen sich hervorragend für Buchungszahlen, Mautgebühren und alle Aufgaben mit vielen Bereichsadditionen und einer abschließenden Ausgabe.

Sie können Bereichsaktualisierungen mit einem Differenzarray bündeln: Markieren Sie l und r + 1 und berechnen Sie anschließend einmal die Präfixsumme, um das Array wiederherzustellen. Schnelle Aktualisierungen, einmaliges Auslesen. ✅