Informática BIT Aula - Contagem de Inversões usando BIT

Aula por Arthur Lobo

Nesta aula, abordaremos uma técnica eficiente para contar a quantidade de inversões em um array usando a estrutura de dados Binary Indexed Tree (BIT).

Conhecimento prévio necessário:

• Binary Indexed Tree (BIT)
• Compressão de coordenadas

O que é uma inversão?

Dado um Array com $N$ elementos $A_1,A_2,...,A_N$, dizemos que $i$ e $j$ estão invertidos (são uma inversão) se $i < j$ e $A_i > A_j$, ou seja, eles estão fora de ordem um em relação ao outro. Formalmente, o par $(i,j)$ é uma inversão $\iff$ $i < j$ e $A_i > A_j$.

A quantidade de inversões é a quantidade de pares $(i,j)$ que são uma inversão. Por exemplo, no array $A = [3,1,2]$ existem duas inversões: $(3, 1)$ e $(3, 2)$.

Comprimindo o Array

Note que a o real valor em cada posição no array $A$ não importa, só importa a os valores de cada posição em relação aos outros valores presentes no array. Por exemplo, os arrays $[3,10,6]$ e $[2,4,3]$ são equivalentes em relação as inversões.

Por conta disso, vamos querer fazer com que os valores no array inicial sejam os menores possíveis, deixando todos eles no intervalo $[1,N]$. Os dois arrays citados a cima virariam $[1,3,2]$, em que todos os valores estão de $1$ até $3$ ($N$).

Para fazer isso, basta utilizarmos a técnica de compreensão de coordenadadas no array inicial. Veja aqui a aula do NOIC sobre compressão de coordenadas: Link da Aula.

Contando as inversões

Vamos contar, para cada $i$, quantos $j$ ($i < j$) existem tal que $(i,j)$ é uma inversão. Nosso objetivo será percorrer o array do final até o começo mantendo uma BIT em que a posição $x$ guarda quantos elementos iguais a $x$ já foram percorridos, então quando estivermos em $i$, basta contarmos quantos elementos $< A_i$ já foram percorridos fazendo uma query na BIT.

Desse jeito, quando estamos em $i$ vamos realizar os seguintes passos:

• Sabemos que já percorremos $A_{i+1},A_{i+2},...,A_N$ e eles já foram somados na BIT.
• Para contar quantos $j$ existem tal que $(i,j)$ é uma inversão, fazemos uma query na BIT contando quantos elementos menores que $A_i$ já foram somados na BIT e adicionamos isso na resposta: quantidade_de_inversões+= $query\_BIT(A_i-1)$.
• Agora adicionamos $A_i$ na BIT, somando $+1$ na posição $A_i$: $update\_BIT(A_i,+1)$.
• Agora podemos seguir para $i-1$, mas com os elementos $A_{i},A_{i+1},...,A_N$ adicionados na BIT.

Por exemplo, no array $A = [3,1,2]$, a query retornaria 0 nas posições $2$ e $3$, mas retornaria $2$ na posição $1$. Já no array $A = [3,2,1]$, a query retornaria $0, 1$ e $2$ nas posições $3,2$ e $1$, respectivamente.

Obs: Não esqueça de utilizar long long para contar as inversões!