Array delle differenze per aggiornamenti su intervalli
Applicare rapidamente molte operazioni di aggiunta su intervalli
Array delle differenze per aggiornamenti su intervalli è una lezione Coding Interview Prep gratuita su CoddyKit. Questa è la lezione 4 di 4. Puoi leggere la lezione completa qui gratuitamente — poi esercitati direttamente nel browser con un editor di codice integrato e un tutor IA disponibile 24/7. Fa parte del percorso di apprendimento Coding Interview Prep, e i tuoi progressi si sincronizzano tra il web e l'app CoddyKit. Il corso Coding Interview Prep include 4 lezioni in totale.
Capovolga il problema
Le somme prefisse permettono di rispondere rapidamente alle query sugli intervalli. Un array delle differenze applica invece rapidamente molti aggiornamenti su intervalli. 🔁
Il metodo lento
Aggiungere un valore a ogni elemento di un intervallo, ripetendolo molte volte, costa O(n) per aggiornamento. Con q aggiornamenti, questo costo aumenta rapidamente.
Memorizzi le variazioni
Invece di modificare ogni cella, registri soltanto dove una variazione inizia e dove termina. Contrassegni gli estremi, non la parte centrale.
Che cosa contiene un array delle differenze
Un array delle differenze memorizza lo scarto tra ogni elemento e quello precedente. Modificare un solo scarto sposta in seguito un intero tratto.
Il trucco dei due contrassegni
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.
diff[l] += v
diff[r + 1] -= vPerché la sottrazione
Il valore aggiunto in l attiva la variazione; quello sottratto in r + 1 la disattiva. Insieme delimitano l'aggiornamento a un solo intervallo.
Applichi tutti gli aggiornamenti in modo efficiente
Ogni aggiornamento consiste soltanto in due scritture nell'array, quindi q aggiornamenti richiedono complessivamente O(q). Il lavoro più impegnativo viene rimandato alla fine.
Ricostruisca l'array finale
Dopo aver inserito tutti i contrassegni, calcoli una somma prefissa dell'array delle differenze. Questa singola passata ricostruisce ogni valore finale.
for i in range(1, n):
diff[i] += diff[i - 1]Dimensioni l'array con una cella di sicurezza
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.
Il costo totale
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).
Dove conviene usarlo
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.
Verifica rapida
Aggiunge v a ogni elemento dall'indice l all'indice r.
Riepilogo
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. ✅
Domande Frequenti
La lezione «Array delle differenze per aggiornamenti su intervalli» è gratuita?
Sì — il testo completo di «Array delle differenze per aggiornamenti su intervalli» è gratuito qui sul web. Per esercitarvi in modo interattivo (un editor di codice integrato e un tutor IA 24/7) e sbloccare il resto del corso Coding Interview Prep, passa a CoddyKit PRO. Il corso Coding Interview Prep include 4 lezioni in totale.
Cosa imparerò in «Array delle differenze per aggiornamenti su intervalli»?
Applicare rapidamente molte operazioni di aggiunta su intervalli Eserciti Coding Interview Prep con codice pratico che esegui direttamente nel browser, e un tutor IA 24/7 risponde alle tue domande mentre lavori sulla lezione.
Ho bisogno di esperienza per iniziare Coding Interview Prep?
Non è richiesta alcuna esperienza precedente. Coding Interview Prep su CoddyKit è strutturato per principianti e studenti avanzati, quindi puoi iniziare da qui o dall'inizio e procedere al tuo ritmo. Questa è la lezione 4 di 4.
Quanto tempo richiede la lezione «Array delle differenze per aggiornamenti su intervalli»?
La maggior parte delle lezioni CoddyKit richiede circa 5–10 minuti. Ogni lezione è breve e interattiva, quindi fai progressi costanti e riprendi esattamente da dove hai lasciato su web e app.
Posso scrivere ed eseguire codice in questa lezione Coding Interview Prep?
Sì. Ogni lezione Coding Interview Prep include un editor di codice integrato, quindi scrivi ed esegui codice reale direttamente nel tuo browser e ricevi feedback istantaneo dall'IA — nessuna configurazione locale necessaria.
Tutte le lezioni di questo corso
- Creare un array delle somme prefisse
- Sommare qualsiasi intervallo con una sottrazione
- Contare i sottoarray con una somma obiettivo
- Array delle differenze per aggiornamenti su intervalli