Differensarrayer för intervalluppdateringar

Prefixsummor besvarar intervallfrågor snabbt. En differensarray vänder på det och tillämpar många intervalluppdateringar snabbt. 🔁

Att lägga till ett värde i varje element i ett intervall, upprepat många gånger, kostar O(n) per uppdatering. För q uppdateringar skenar den kostnaden.

I stället för att ändra varje cell registrerar Ni bara var en förändring börjar och var den slutar. Markera kanterna, inte mitten.

En differensarray lagrar skillnaden mellan varje element och elementet före det. Om Ni ändrar en enda skillnad förskjuts ett helt efterföljande intervall.

För att lägga till v från l till r lägger Ni till v vid index l och subtraherar v vid index r + 1. Bara två ändringar täcker hela intervallet.

Plustecknet vid l aktiverar förändringen, medan minustecknet vid r + 1 stänger av den igen. Tillsammans begränsar de uppdateringen till ett intervall.

Varje uppdatering består bara av två array-skrivningar, så q uppdateringar tar totalt O(q). Det tunga arbetet skjuts upp till slutet.

När alla markeringar har placerats tar Ni en prefixsumma av differensarrayen. Det enda passet återskapar varje slutligt värde.

Gör arrayen en cell längre så att r + 1 aldrig hamnar utanför slutet. Den extra skyddsplatsen förhindrar indexfel.

Ni lägger O(q) på att markera uppdateringarna och gör sedan ett pass på O(n) för att återskapa arrayen. Den sammanlagda kostnaden är mycket lägre än den naiva O(n gånger q).

Differensarrayer är utmärkta för bokningsantal, vägavgifter och alla problem med många intervallsadditioner och en enda slutlig avläsning.

Ni kan samla intervalluppdateringar med en differensarray: markera l och r + 1 och ta sedan en enda prefixsumma för att återskapa arrayen. Snabba uppdateringar, en enda avläsning. ✅