Differensarrays til intervalopdateringer

Præfikssummer besvarede intervalforespørgsler hurtigt. Et differensarray vender det om, så du hurtigt kan udføre mange intervalopdateringer. 🔁

At lægge en værdi til hvert element i et interval, gentaget mange gange, koster O(n) pr. opdatering. For q opdateringer eksploderer den omkostning.

I stedet for at ændre hver celle skal du kun registrere, hvor en ændring begynder, og hvor den slutter. Markér kanterne, ikke midten.

Et differensarray gemmer forskellen mellem hvert element og det foregående. Hvis du ændrer én forskel, forskyder det et helt efterfølgende stykke.

For at lægge v til fra l til r skal du lægge v til ved indeks l og trække v fra ved indeks r + 1. Bare to ændringer dækker hele intervallet.

Plusset ved l aktiverer ændringen, og minusset ved r + 1 slår den fra igen. Tilsammen begrænser de opdateringen til ét interval.

Hver opdatering består kun af to skrivninger i arrayet, så q opdateringer tager O(q) i alt. Det tunge arbejde udsættes til sidst.

Når alle markeringer er placeret, skal du beregne en præfikssum af differensarrayet. Dette ene gennemløb genskaber alle de endelige værdier.

Gør arrayet én plads længere, så r + 1 aldrig løber ud over enden. Den ekstra sikkerhedsplads forhindrer indeksfejl.

Du bruger O(q) på at markere opdateringerne og ét gennemløb på O(n) for at genskabe arrayet. Den samlede omkostning er langt mindre end den naive O(n gange q).

Differensarrays er nyttige til optælling af bookinger, vejafgifter og alle problemer med mange intervaltilføjelser og én endelig aflæsning.

Du kan samle intervalopdateringer i et differensarray: markér l og r + 1, og beregn derefter præfikssummen én gang for at genskabe arrayet. Hurtige opdateringer, én aflæsning. ✅