Inversiones con un BIT
Cuente pares fuera de orden de forma eficiente
Inversiones con un BIT es una lección gratuita de Competitive Programming Academy en CoddyKit. Esta es la lección 2 de 4. Puedes leer la lección completa abajo gratuitamente — luego la practicas en el navegador con un editor de código integrado y un tutor de IA 24/7. Forma parte de la ruta de aprendizaje de Competitive Programming Academy, y tu progreso se sincroniza en la web y la app de CoddyKit. El curso de Competitive Programming Academy incluye 4 lecciones en total.
Qué es una inversión
Una inversión es un par i < j donde a[i] > a[j]. Es un único par fuera de orden, y contarlas mide cuánto está desordenado un array.
Por qué importan las inversiones
El número de inversiones equivale a la cantidad de intercambios que realizaría un ordenamiento de burbuja. Los problemas de concursos las esconden en preguntas sobre posiciones y desorden.
El recuento ingenuo es demasiado lento
Comprobar cada par cuesta O(n^2). Para n cercano a 100000, son diez mil millones de comprobaciones, muy por encima del límite de tiempo. Necesitamos algo más inteligente. 🐢
La idea del BIT
Recorra el array de izquierda a derecha y pregúntese: ¿cuántos elementos anteriores son mayores que el actual? Un árbol de Fenwick responde a esa pregunta sobre la marcha.
Contar por frecuencia
El BIT almacena una tabla de frecuencias de los valores. update(v, 1) registra que el valor v ha aparecido hasta el momento en nuestro recorrido.
update(v, 1)Mayor significa sufijo
Los valores anteriores mayores que v son la cantidad de elementos vistos menos los que son menores o iguales que v. En el elemento i-ésimo, eso es i menos query(v).
inv += i - query(v)Compresión de coordenadas
Si los valores son grandes o negativos, asígneles primero posiciones del 1..n. Esta compresión mantiene pequeño el BIT sin cambiar ningún orden.
rank = {v: i for i, v in enumerate(sorted(set(a)), 1)}El recorrido completo
Recorra el array, añada al total la cantidad de elementos mayores y después inserte el valor actual. El total acumulado es el número de inversiones.
for i, v in enumerate(a):
inv += i - query(rank[v])
update(rank[v], 1)Se ejecuta en n log n
Cada elemento activa una consulta y una actualización, ambas en O(log n). El recuento completo termina en tiempo O(n log n). 🚀
Merge sort es su pariente
Merge sort también cuenta inversiones en O(n log n) durante su paso de mezcla. La versión con BIT suele ser más breve de escribir bajo presión.
Tenga cuidado con el desbordamiento
Las inversiones pueden alcanzar aproximadamente n al cuadrado dividido entre dos, una cantidad enorme. Los enteros de Python no tienen un límite fijo, pero en otros lenguajes necesitaría un tipo de 64 bits.
Comprobación rápida
Compruebe cuánto ha entendido sobre el coste del recorrido.
Repaso: contar el desorden
Contó inversiones en O(n log n) recorriendo de izquierda a derecha y preguntando a un BIT cuántos valores mayores habían aparecido antes. Comprima los valores cuando sea necesario. ✅
Preguntas frecuentes
¿La lección «Inversiones con un BIT» es gratis?
Sí — el texto completo de «Inversiones con un BIT» es gratis para leer aquí en la web. Para practicarla de forma interactiva (editor de código integrado y tutor de IA 24/7) y desbloquear el resto del curso de Competitive Programming Academy, actualiza a CoddyKit PRO. El curso de Competitive Programming Academy incluye 4 lecciones en total.
¿Qué aprenderé en «Inversiones con un BIT»?
Cuente pares fuera de orden de forma eficiente Practicas Competitive Programming Academy con código real que ejecutas directamente en el navegador, y un tutor de IA 24/7 responde tus preguntas mientras trabajas en la lección.
¿Necesito experiencia previa para empezar Competitive Programming Academy?
No se requiere experiencia previa. Competitive Programming Academy en CoddyKit está estructurado para principiantes hasta estudiantes avanzados, así que puedes empezar aquí o desde el inicio y avanzar a tu ritmo. Esta es la lección 2 de 4.
¿Cuánto tiempo toma la lección «Inversiones con un BIT»?
La mayoría de las lecciones de CoddyKit toman alrededor de 5–10 minutos. Cada una es compacta e interactiva, así que avanzas constantemente y retomas exactamente por donde dejaste en la web y la app.
¿Puedo escribir y ejecutar código en esta lección de Competitive Programming Academy?
Sí. Cada lección de Competitive Programming Academy incluye un editor de código integrado, así que escribes y ejecutas código real directamente en tu navegador y obtienes retroalimentación instantánea de IA — sin configuración local necesaria.
Todas las lecciones de este curso
- Árbol de Fenwick para sumas prefijas
- Inversiones con un BIT
- Árbol de segmentos: construcción y consultas
- Propagación diferida para actualizaciones de rangos