Segment tree: costruzione e query
Calcolare minimo, massimo o somma su un intervallo in log n
Segment tree: costruzione e query è una lezione Coding Interview Prep gratuita su CoddyKit. Questa è la lezione 3 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.
Oltre l'albero di Fenwick
Un albero di Fenwick è eccellente per le somme, ma un segment tree gestisce minimo, massimo, MCD e altro ancora. È lo strumento flessibile per eccellenza nelle interrogazioni sugli intervalli.
Un albero sugli intervalli
Ogni nodo possiede un intervallo dell'array. La radice copre tutto, mentre i figli lo dividono a metà finché le foglie contengono singoli elementi.
Memorizzazione in un array
Si memorizza l'albero in un array lineare di dimensione 2n o 4n. Il nodo 1 è la radice; i figli del nodo i si trovano in 2i e 2i+1.
seg = [0] * (2 * n)Le foglie contengono i dati
Nella versione iterativa, i valori originali si trovano nella seconda metà dell'array, agli indici da n a 2n-1.
for i in range(n):
seg[n + i] = a[i]Costruire dal basso verso l'alto
Ogni nodo interno è il combine dei suoi due figli. Li si riempie da n-1 fino a 1 e l'intero albero è pronto.
for i in range(n - 1, 0, -1):
seg[i] = seg[2*i] + seg[2*i+1]L'operazione combine
La funzione combine definisce l'albero. Si usi plus per le somme, min per i minimi o max per i massimi. Sostituendola, si modifica l'interrogazione.
def combine(x, y):
return min(x, y)Aggiornamento puntuale, poi risalita
Per modificare un valore, si imposta la foglia e si risale fino alla radice, ricalcolando lungo il percorso ogni genitore a partire dai suoi due figli.
i += n
seg[i] = value
while i > 1:
i //= 2
seg[i] = combine(seg[2*i], seg[2*i+1])Interrogare un intervallo semiaperto
Le interrogazioni sugli intervalli esaminano entrambe le estremità, combinando nel risultato i nodi ai bordi. L'intervallo è semiaperto: comprende l fino a prima di r.
Il ciclo iterativo di interrogazione
Si spostano l e r l'uno verso l'altro. Quando un indice si trova su un bordo dispari, si include quel nodo prima di spostare il puntatore.
while l < r:
if l & 1: res = combine(res, seg[l]); l += 1
if r & 1: r -= 1; res = combine(res, seg[r])
l //= 2; r //= 2Logaritmico da entrambe le estremità
La costruzione richiede O(n), mentre ogni aggiornamento e interrogazione richiede O(log n). È questo equilibrio a rendere i segment tree così versatili.
Attenzione all'elemento neutro
Si inizializza il risultato con l'elemento neutro dell'operazione: 0 per la somma, infinito per il minimo e meno infinito per il massimo. Un'inizializzazione errata produce risultati errati.
res = float('inf')Verifica rapida
Dove si trovano i dati grezzi nell'albero iterativo?
Riepilogo: intervalli flessibili
Ha costruito un segment tree: foglie nella seconda metà, genitori ottenuti tramite combine, con aggiornamenti e interrogazioni in O(log n) per somme, minimi o massimi. 🌳
Domande Frequenti
La lezione «Segment tree: costruzione e query» è gratuita?
Sì — il testo completo di «Segment tree: costruzione e query» è 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 «Segment tree: costruzione e query»?
Calcolare minimo, massimo o somma su un intervallo in log n 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 3 di 4.
Quanto tempo richiede la lezione «Segment tree: costruzione e query»?
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
- Albero di Fenwick per le somme prefisse
- Inversioni con un BIT
- Segment tree: costruzione e query
- Lazy propagation per aggiornamenti su intervalli