Inversões com uma BIT
Conte pares fora de ordem com eficiência.
Inversões com uma BIT é uma aula grátis de Coding Interview Prep no CoddyKit. Esta é a aula 2 de 4. Você pode ler a aula completa abaixo gratuitamente — depois pratica ao vivo no navegador com um editor de código integrado e um tutor de IA 24/7. Faz parte do caminho de aprendizado de Coding Interview Prep, e seu progresso é sincronizado entre a web e o app CoddyKit. O curso de Coding Interview Prep inclui 4 aulas no total.
O que é uma inversão
Uma inversão é um par i < j para o qual a[i] > a[j]. Trata-se de um único par fora de ordem, e contá-los mede o quanto um vetor está desordenado.
Por que as inversões importam
A quantidade de inversões é igual ao número de trocas que uma ordenação por bolhas sort faria. Problemas de competição escondem esse conceito em perguntas sobre classificação e desordem.
A contagem ingênua é lenta demais
Verificar todos os pares custa O(n^2). Para n próximo de 100000, isso representa dez bilhões de verificações, muito além do limite de tempo. Precisamos de algo mais inteligente. 🐢
A ideia da BIT
Percorra o vetor da esquerda para a direita e pergunte: quantos elementos anteriores são maiores que o atual? Uma árvore de Fenwick responde a isso durante o percurso.
Conte por frequência
A BIT armazena uma tabela de frequências dos valores. A atualização de v em 1 registra que o valor v já apareceu durante o percurso.
update(v, 1)Maior significa sufixo
Os valores anteriores maiores que v são a quantidade de valores vistos menos a quantidade até v. Isso corresponde a i menos a consulta(v) no i-ésimo elemento.
inv += i - query(v)Compressão de coordenadas
Se os valores forem grandes ou negativos, mapeie-os primeiro para as classificações de 1 a n. Essa compressão mantém a BIT pequena sem alterar nenhuma ordem.
rank = {v: i for i, v in enumerate(sorted(set(a)), 1)}O percurso completo
Percorra o vetor, adicione ao total a quantidade de valores maiores e depois insira o valor atual. O total acumulado é a quantidade de inversões.
for i, v in enumerate(a):
inv += i - query(rank[v])
update(rank[v], 1)Executa em n log n
Cada elemento provoca uma consulta e uma atualização, ambas em O(log n). A contagem inteira termina em tempo O(n log n). 🚀
A ordenação por intercalação é a parente
A ordenação por intercalação também conta inversões em O(n log n) durante sua etapa de intercalação. A versão com BIT costuma ser mais curta de escrever sob pressão.
Cuidado com o estouro da contagem
O número de inversões pode chegar a aproximadamente n ao quadrado dividido por dois, o que é enorme. Os inteiros do Python não têm limite, mas em outras linguagens você precisaria de um tipo de 64 bits.
Verificação rápida
Teste sua compreensão do custo do percurso.
Recapitulação: contando a desordem
Você contou inversões em O(n log n), percorrendo o vetor da esquerda para a direita e perguntando a uma BIT quantos valores maiores apareceram antes. Comprima os valores quando necessário. ✅
Perguntas Frequentes
A aula “Inversões com uma BIT” é grátis?
Sim — o texto completo de “Inversões com uma BIT” é grátis para ler aqui na web. Para praticá-la interativamente (um editor de código integrado e um tutor de IA 24/7) e desbloquear o restante do curso de Coding Interview Prep, atualize para CoddyKit PRO. O curso de Coding Interview Prep inclui 4 aulas no total.
O que vou aprender em “Inversões com uma BIT”?
Conte pares fora de ordem com eficiência. Você pratica Coding Interview Prep com código prático que executa diretamente no navegador, e um tutor de IA 24/7 responde suas dúvidas enquanto trabalha na aula.
Preciso ter experiência prévia para começar Coding Interview Prep?
Nenhuma experiência prévia é necessária. Coding Interview Prep no CoddyKit é estruturado para alunos iniciantes até avançados, então você pode começar aqui ou desde o início e aprender no seu ritmo. Esta é a aula 2 de 4.
Quanto tempo leva a aula “Inversões com uma BIT”?
A maioria das aulas CoddyKit leva cerca de 5–10 minutos. Cada uma é compacta e interativa, então você faz progresso constante e retoma exatamente de onde parou entre web e app.
Posso escrever e executar código nesta aula de Coding Interview Prep?
Sim. Cada aula de Coding Interview Prep inclui um editor de código integrado, então você escreve e executa código real direto no navegador e recebe feedback de IA instantaneamente — nenhuma configuração local necessária.
Todas as aulas deste curso
- Árvore de Fenwick para Somas de Prefixos
- Inversões com uma BIT
- Árvore de Segmentos: Construção e Consulta
- Propagação Preguiçosa para Atualizações de Intervalos