Inversions avec un BIT
Compter efficacement les paires dans le mauvais ordre
Inversions avec un BIT est une leçon Competitive Programming Academy gratuite sur CoddyKit. Ceci est la leçon 2 sur 4. Tu peux lire la leçon complète ci-dessous gratuitement — puis la pratiquer en direct dans le navigateur avec un éditeur de code intégré et un tuteur IA 24/7. Elle fait partie du parcours d'apprentissage Competitive Programming Academy, et ta progression se synchronise sur le web et l'application CoddyKit. Le cours Competitive Programming Academy comprend 4 leçons au total.
Qu'est-ce qu'une inversion
Une inversion est une paire i < j telle que a[i] > a[j]. Il s'agit d'une seule paire dans le désordre, et leur comptage mesure à quel point un tableau n'est pas trié.
Pourquoi les inversions sont importantes
Le nombre d'inversions est égal au nombre d'échanges qu'effectuerait un tri à bulles. Les problèmes de concours les dissimulent dans des questions de classement et de désordre.
Le comptage naïf est trop lent
Vérifier chaque paire coûte O(n^2). Pour n proche de 100000, cela représente dix milliards de vérifications, bien au-delà de la limite de temps. Il nous faut une méthode plus intelligente. 🐢
L'idée du BIT
Parcourez le tableau de gauche à droite et demandez-vous : combien d'éléments précédents sont plus grands que l'élément actuel ? Un arbre de Fenwick répond à cette question au fil du parcours.
Compter par fréquence
Le BIT stocke un tableau de fréquences des valeurs. L'expression update(v, 1) indique que la valeur v est apparue jusque-là dans notre parcours.
update(v, 1)Plus grand signifie suffixe
Les valeurs précédentes plus grandes que v correspondent au nombre de valeurs déjà vues moins celles qui sont inférieures ou égales à v. À la i-ème position, cela donne i moins query(v).
inv += i - query(v)Compression des coordonnées
Si les valeurs sont grandes ou négatives, associez-leur d'abord les rangs 1..n. Cette compression garde le BIT compact sans modifier le moindre ordre.
rank = {v: i for i, v in enumerate(sorted(set(a)), 1)}Le parcours complet
Parcourez le tableau, ajoutez chaque nombre de valeurs plus grandes au total, puis insérez la valeur actuelle. Le total cumulé est votre nombre d'inversions.
for i, v in enumerate(a):
inv += i - query(rank[v])
update(rank[v], 1)Cela s'exécute en n log n
Chaque élément déclenche une requête et une mise à jour, toutes deux en O(log n). Le comptage complet s'achève donc en O(n log n). 🚀
Le tri fusion est son cousin
Le tri fusion compte lui aussi les inversions en O(n log n) pendant son étape de fusion. La version avec BIT est souvent plus courte à écrire sous la pression.
Attention au dépassement du compteur
Le nombre d'inversions peut atteindre environ n au carré divisé par deux, ce qui est énorme. Les entiers Python sont non bornés, mais dans d'autres langages, vous auriez besoin d'un type 64 bits.
Vérification rapide
Vérifiez votre compréhension du coût du parcours.
Récapitulatif : compter le désordre
Vous avez compté les inversions en O(n log n) en parcourant le tableau de gauche à droite et en demandant à un BIT combien de valeurs plus grandes étaient apparues auparavant. Compressez les valeurs si nécessaire. ✅
Questions Fréquemment Posées
La leçon « Inversions avec un BIT » est-elle gratuite ?
Oui — le texte complet de « Inversions avec un BIT » est gratuit à lire ici sur le web. Pour la pratiquer de manière interactive (un éditeur de code intégré et un tuteur IA 24/7) et déverrouiller le reste du cours Competitive Programming Academy, passe à CoddyKit PRO. Le cours Competitive Programming Academy comprend 4 leçons au total.
Qu'est-ce que j'apprendrai dans « Inversions avec un BIT » ?
Compter efficacement les paires dans le mauvais ordre Tu pratiques Competitive Programming Academy avec du code pratique que tu exécutes directement dans le navigateur, et un tuteur IA 24/7 répond à tes questions au fur et à mesure que tu avances dans la leçon.
Dois-je avoir de l'expérience pour commencer Competitive Programming Academy ?
Aucune expérience préalable n'est requise. Competitive Programming Academy sur CoddyKit est structuré pour les débutants jusqu'aux apprenants avancés, donc tu peux commencer ici ou depuis le début et avancer à ton rythme. Ceci est la leçon 2 sur 4.
Combien de temps prend la leçon « Inversions avec un BIT » ?
La plupart des leçons CoddyKit prennent environ 5–10 minutes. Chacune est courte et interactive, tu progresses régulièrement et tu repiques exactement où tu t'es arrêté sur le web et l'app.
Peux-tu écrire et exécuter du code dans cette leçon Competitive Programming Academy ?
Oui. Chaque leçon Competitive Programming Academy inclut un éditeur de code intégré, tu écris et exécutes du vrai code directement dans ton navigateur et tu reçois des retours IA instantanés — aucune configuration locale requise.
Toutes les leçons de ce cours
- Arbre de Fenwick pour les sommes préfixes
- Inversions avec un BIT
- Arbre de segments : construction et requêtes
- Propagation paresseuse pour les mises à jour de plages