Verschilarrays voor bereikupdates

Prefixesommen maakten bereikopvragingen snel. Een verschilarray draait dat om en maakt veel bereikupdates snel. 🔁

Een waarde aan elk element in een bereik toevoegen kost bij veel herhalingen O(n) per update. Over q updates heen loopt die kost enorm op.

In plaats van elke cel aan te raken, noteer je alleen waar een wijziging begint en waar die eindigt. Markeer de randen, niet het midden.

Een verschilarray bewaart het verschil tussen elk element en het vorige element. Als je één verschil aanpast, verschuift een hele reeks verderop.

Om v toe te voegen van l tot en met r, voeg je v toe op index l en trek je v af op index r + 1. Met slechts twee bewerkingen dek je het hele bereik af.

De plus op l schakelt de wijziging in; de min op r + 1 schakelt die weer uit. Samen begrenzen ze de update tot één bereik.

Elke update bestaat uit slechts twee schrijfbewerkingen in de array, dus q updates kosten in totaal O(q). Het zware werk stel je uit tot het einde.

Nadat alle markeringen zijn geplaatst, bereken je een prefixsom van de verschilarray. Met die ene doorgang reconstrueer je elke uiteindelijke waarde.

Maak de array één cel langer, zodat r + 1 nooit buiten het einde valt. Dat extra beschermingsvak voorkomt indexfouten.

Je besteedt O(q) aan het markeren van updates en één doorgang van O(n) aan het opnieuw opbouwen. De gecombineerde kost ligt ver onder de eenvoudige O(n maal q).

Verschilarrays zijn ideaal voor boekingsaantallen, toltarieven en elk probleem met veel bewerkingen voor bereikoptellingen en één uiteindelijke uitlezing.

Je kunt updates voor bereiken bundelen met een verschilarray: markeer l en r + 1 en bereken daarna één keer de prefixsom om alles opnieuw op te bouwen. Snelle updates, één uitlezing. ✅