Inversioni con un BIT
Contare in modo efficiente le coppie fuori ordine
Inversioni con un BIT è una lezione Competitive Programming Academy gratuita su CoddyKit. Questa è la lezione 2 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.
Che cos'è un'inversione
Un'inversione è una coppia i < j per cui a[i] > a[j]. È una singola coppia fuori ordine e il suo conteggio misura quanto un array sia disordinato.
Perché le inversioni sono importanti
Il conteggio delle inversioni è uguale al numero di scambi che eseguirebbe un bubble sort. I problemi di programmazione competitiva lo nascondono spesso in domande su classifiche e disordine.
Il conteggio ingenuo è troppo lento
Controllare ogni coppia richiede O(n^2). Per n intorno a 100000, significa dieci miliardi di controlli, ben oltre il limite di tempo. Serve una soluzione più intelligente. 🐢
L'idea del BIT
Si scorre l'array da sinistra a destra chiedendosi: quanti elementi precedenti sono maggiori di quello corrente? Un albero di Fenwick risponde man mano a questa domanda.
Contare per frequenza
Il BIT memorizza una tabella delle frequenze dei valori. update(v, 1) registra che il valore v è comparso finora durante la scansione.
update(v, 1)I valori maggiori formano un suffisso
I valori precedenti maggiori di v sono il numero di elementi già visti meno quelli fino a v. Per l'elemento i-esimo, questo corrisponde a i meno query(v).
inv += i - query(v)Compressione delle coordinate
Se i valori sono grandi o negativi, prima li si mappa sui ranghi 1..n. Questa compressione mantiene piccolo il BIT senza modificare alcun ordine.
rank = {v: i for i, v in enumerate(sorted(set(a)), 1)}La scansione completa
Si scorre l'array, si aggiunge al totale il conteggio dei valori maggiori e poi si inserisce il valore corrente. Il totale progressivo è il conteggio delle inversioni.
for i, v in enumerate(a):
inv += i - query(rank[v])
update(rank[v], 1)Complessità n log n
Ogni elemento attiva un'interrogazione e un aggiornamento, entrambi in O(log n). L'intero conteggio termina in tempo O(n log n). 🚀
Merge sort è il parente
Anche merge sort conta le inversioni in O(n log n) durante il passaggio di fusione. La versione con BIT è spesso più breve da scrivere sotto pressione.
Attenzione all'overflow del conteggio
Le inversioni possono arrivare a circa n al quadrato diviso due, un valore enorme. Gli interi Python non hanno un limite superiore, ma negli altri linguaggi serve un tipo 64-bit.
Verifica rapida
Verifichi di aver compreso il costo della scansione.
Riepilogo: contare il disordine
Ha contato le inversioni in O(n log n) scorrendo da sinistra a destra e chiedendo a un BIT quanti valori maggiori fossero comparsi prima. Quando necessario, comprima i valori. ✅
Domande Frequenti
La lezione «Inversioni con un BIT» è gratuita?
Sì — il testo completo di «Inversioni con un BIT» è 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 «Inversioni con un BIT»?
Contare in modo efficiente le coppie fuori ordine 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 2 di 4.
Quanto tempo richiede la lezione «Inversioni con un BIT»?
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