Albero di Fenwick per le somme prefisse
Aggiornare un punto ed eseguire query prefisse in log n
Albero di Fenwick per le somme prefisse è una lezione Coding Interview Prep gratuita su CoddyKit. Questa è la lezione 1 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.
Perché gli array dei prefissi non bastano
Un semplice array delle somme dei prefissi risponde immediatamente alle richieste sugli intervalli, ma un singolo aggiornamento obbliga a ricostruirlo. Con molti aggiornamenti, l'operazione diventa lenta. ⏱️
Ecco l'albero di Fenwick
L'albero di Fenwick, o BIT, supporta sia gli aggiornamenti puntuali sia le interrogazioni dei prefissi in O(log n). È la scelta ideale per i totali progressivi dinamici.
Indicizzato a partire da uno
Un albero di Fenwick usa un array indicizzato a partire da 1. L'indice 0 funge da sentinella inattiva, così tutti i dati reali iniziano dalla posizione 1.
tree = [0] * (n + 1)La magia del bit meno significativo
Ogni indice copre un blocco di valori. La dimensione del blocco è uguale a i & -i, il bit meno significativo impostato a 1 di i. Questo semplice trucco alimenta l'intero albero.
lowbit = i & -iAggiornare un singolo punto
Per aggiungere un valore nella posizione i, si procede in avanti di un lowbit alla volta, visitando ogni blocco che contiene i.
while i <= n:
tree[i] += delta
i += i & -iInterrogare una somma di prefisso
Per sommare i primi i valori, si procede all'indietro sottraendo il lowbit a ogni passo, fino a raggiungere zero.
s = 0
while i > 0:
s += tree[i]
i -= i & -iEntrambi i cicli sono logaritmici
A ogni iterazione, ciascun ciclo disattiva un bit, quindi viene eseguito al massimo log n volte. Ecco perché sia l'aggiornamento sia l'interrogazione rimangono rapidi.
Somma su un intervallo da due prefissi
Per ottenere la somma da l a r, si calcola prefix(r) meno prefix(l-1), proprio come con un array statico dei prefissi, ma con aggiornamenti ora poco costosi.
range_sum = query(r) - query(l - 1)Costruire l'albero
La costruzione più semplice consiste nel chiamare update per ogni valore iniziale. Ha complessità O(n log n) ed è abbastanza rapida per la maggior parte delle gare.
for i, v in enumerate(a, 1):
update(i, v)Un ingombro minimo in memoria
Un albero di Fenwick richiede un solo array di dimensione n+1. Questo ingombro compatto è uno dei motivi per cui è tanto apprezzato nelle gare. 💾
Quando scegliere un BIT
Si scelga un albero di Fenwick quando si alternano aggiornamenti puntuali con interrogazioni di prefissi o somme su intervalli. È breve da implementare e difficile da superare.
Verifica rapida
Consolidiamo il modo in cui si spostano i cicli.
Riepilogo: basi del BIT
Ha conosciuto l'albero di Fenwick: indicizzato a partire da 1, basato su i & -i, con aggiornamento puntuale e interrogazione del prefisso entrambi in O(log n). In seguito, lo si userà per contare le inversioni. 🎯
Domande Frequenti
La lezione «Albero di Fenwick per le somme prefisse» è gratuita?
Sì — il testo completo di «Albero di Fenwick per le somme prefisse» è 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 «Albero di Fenwick per le somme prefisse»?
Aggiornare un punto ed eseguire query prefisse 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 1 di 4.
Quanto tempo richiede la lezione «Albero di Fenwick per le somme prefisse»?
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