Lazy propagation per aggiornamenti su intervalli
Rimandare gli aggiornamenti su intervalli interi
Lazy propagation per aggiornamenti su intervalli è una lezione Competitive Programming Academy 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 Competitive Programming Academy, e i tuoi progressi si sincronizzano tra il web e l'app CoddyKit. Il corso Competitive Programming Academy include 4 lezioni in totale.
Il problema degli aggiornamenti su intervalli
E se un'interrogazione richiedesse di aggiungere 5 a ogni elemento da l a r? Visitare ogni foglia richiede O(n) per aggiornamento, troppo per molti aggiornamenti su intervalli. 😰
L'idea lazy
La lazy propagation consente a un nodo di ricordare una modifica in sospeso senza propagarla subito ai figli. Il lavoro viene rimandato finché quei figli non sono realmente necessari.
Un secondo array per il lavoro in sospeso
Accanto all'albero si mantiene un array lazy. lazy[node] memorizza un aggiornamento che si applica all'intero intervallo del nodo, ma che non è ancora stato propagato verso il basso.
lazy = [0] * (4 * n)Applicare a un intero nodo
Quando un aggiornamento copre completamente un nodo, si modifica il valore memorizzato e si accumula la modifica in lazy, poi ci si ferma. Non è necessario scendere nell'albero.
seg[node] += (r - l + 1) * val
lazy[node] += valPropagare verso il basso prima di scendere
Prima di visitare i figli, si esegue il push down di ogni valore lazy in sospeso verso entrambi. In questo modo i figli sono corretti esattamente quando vengono letti.
def push_down(node, l, r):
if lazy[node]:
apply(2*node, l, mid)
apply(2*node+1, mid+1, r)
lazy[node] = 0Tre casi per ogni nodo
In ogni nodo, l'intervallo dell'interrogazione è disgiunto, copre completamente il nodo oppure lo copre parzialmente. Rispettivamente, si salta, si applica lazy oppure si ricorre su entrambe le metà.
Gli aggiornamenti lazy restano logaritmici
Un aggiornamento su intervallo visita solo O(log n) nodi, perché i nodi coperti completamente terminano subito. Questo è l'intero vantaggio dell'approccio lazy. ⚡
Anche le query scendono
Anche le query su intervalli devono propagare verso il basso prima della ricorsione, così leggono i valori aggiornati dei figli. Dimenticarsene è il classico errore nella propagazione lazy.
Ricalcolare dopo la ricorsione
Dopo aver aggiornato i figli, ricombini il nodo padre a partire da loro. Questa risalita mantiene coerente ogni nodo interno con il proprio sottoalbero.
seg[node] = seg[2*node] + seg[2*node+1]Assegnazione e somma
La propagazione lazy funziona con molte operazioni, ma assegnazione e somma si combinano in modo diverso. Stabilire come unire due aggiornamenti in sospeso prima di scrivere il codice.
Quando conviene usare la propagazione lazy
Ricorra alla propagazione lazy solo quando servono davvero aggiornamenti su intervalli. Per i soli aggiornamenti puntuali, un semplice albero dei segmenti è più facile da usare e sufficiente.
Verifica rapida
Che cosa deve accadere prima di ricorrere sui figli di un nodo?
Riepilogo: aggiornamenti differiti
Ha imparato la propagazione lazy: memorizzare le modifiche in sospeso, propagarle verso il basso prima di scendere, ricalcolare verso l'alto dopo, ottenendo aggiornamenti su intervalli in O(log n). 🎉
Domande Frequenti
La lezione «Lazy propagation per aggiornamenti su intervalli» è gratuita?
Sì — il testo completo di «Lazy propagation 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 Competitive Programming Academy, passa a CoddyKit PRO. Il corso Competitive Programming Academy include 4 lezioni in totale.
Cosa imparerò in «Lazy propagation per aggiornamenti su intervalli»?
Rimandare gli aggiornamenti su intervalli interi Eserciti Competitive Programming Academy 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 Competitive Programming Academy?
Non è richiesta alcuna esperienza precedente. Competitive Programming Academy 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 «Lazy propagation 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 Competitive Programming Academy?
Sì. Ogni lezione Competitive Programming Academy 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
- Albero di Fenwick per le somme prefisse
- Inversioni con un BIT
- Segment tree: costruzione e query
- Lazy propagation per aggiornamenti su intervalli