Array delle differenze per aggiornamenti su intervalli

Le somme prefisse permettono di rispondere rapidamente alle query sugli intervalli. Un array delle differenze applica invece rapidamente molti aggiornamenti su intervalli. 🔁

Aggiungere un valore a ogni elemento di un intervallo, ripetendolo molte volte, costa O(n) per aggiornamento. Con q aggiornamenti, questo costo aumenta rapidamente.

Invece di modificare ogni cella, registri soltanto dove una variazione inizia e dove termina. Contrassegni gli estremi, non la parte centrale.

Un array delle differenze memorizza lo scarto tra ogni elemento e quello precedente. Modificare un solo scarto sposta in seguito un intero tratto.

Per aggiungere v da l a r, aggiunga v all'indice l e sottragga v all'indice r + 1. Bastano due modifiche per coprire l'intero intervallo.

Il valore aggiunto in l attiva la variazione; quello sottratto in r + 1 la disattiva. Insieme delimitano l'aggiornamento a un solo intervallo.

Ogni aggiornamento consiste soltanto in due scritture nell'array, quindi q aggiornamenti richiedono complessivamente O(q). Il lavoro più impegnativo viene rimandato alla fine.

Dopo aver inserito tutti i contrassegni, calcoli una somma prefissa dell'array delle differenze. Questa singola passata ricostruisce ogni valore finale.

Renda l'array più lungo di una cella, così r + 1 non oltrepasserà mai la fine. Questa cella di sicurezza aggiuntiva evita gli errori di indice.

Dedica O(q) a contrassegnare gli aggiornamenti e una passata O(n) a ricostruire l'array. Il costo complessivo è molto inferiore al metodo ingenuo O(n per q).

Gli array delle differenze sono ideali per contare le prenotazioni, calcolare i pedaggi stradali e risolvere qualsiasi problema con molte operazioni di somma su intervalli e una sola lettura finale.

Ora può raggruppare gli aggiornamenti su intervalli con un array delle differenze: contrassegni l e r + 1, poi calcoli una sola somma prefissa per ricostruire l'array. Aggiornamenti rapidi, una sola lettura. ✅