A contagem de inversão para uma array indica - a que distância (ou perto) a array está de ser classificada. Se a array já estiver classificada, a contagem de inversão será 0. Se a array for classificada na ordem inversa, essa contagem de inversão será o máximo. 
Dois elementos a [i] e a [j] formam uma inversão se a [i]> a [j] ei <j. Para simplificar, podemos assumir que todos os elementos são únicos.
Exemplo: 

Input: arr[] = {8, 4, 2, 1}
Output: 6
Explanation: Given array has six inversions:
(8,4), (4,2), (8,2), (8,1), (4,1), (2,1).     


Input: arr[] = {3, 1, 2}
Output: 2
Explanation: Given array has two inversions:
(3,1), (3,2).

Recomendamos fortemente que você clique aqui e pratique antes de prosseguir para a solução.

Já discutimos os métodos abaixo para resolver a contagem de inversão:  

1. Classificação de mesclagem ingênua e modificada
2. Usando AVL Tree

Recomendamos que você consulte a árvore indexada binária (BIT) antes de continuar lendo este post. 
Solução usando BIT de tamanho Θ (maxElement):  

• Abordagem: Percorra a array e, para cada índice, encontre o número de elementos menores em seu lado direito da array. Isso pode ser feito usando o BIT. Some as contagens de todos os índices na array e imprima a soma.
• Antecedentes do BIT: 
  1. O BIT suporta basicamente duas operações para uma array arr [] de tamanho n: 
     1. Soma dos elementos até arr [i] no tempo O (Log n).
     2. Atualize um elemento da array em tempo O (Log n).
  2. O BIT é implementado usando uma array e funciona na forma de árvores. Observe que há duas maneiras de ver o BIT como uma árvore. 
     1. A operação de soma onde o pai do índice x é “x - (x & -x)”.
     2. A operação de atualização onde o pai do índice x é “x + (x & -x)”.
• Algoritmo: 
  1. Crie um BIT, para encontrar a contagem dos elementos menores no BIT para um determinado número e também um resultado variável = 0 .
  2. Percorra a array do início ao fim.
  3. Para cada índice, verifique quantos números a menos do que o elemento atual estão presentes no BIT e adicione-o ao resultado
  4. Para obter a contagem de elementos menores, getSum() de BIT é usado.
  5. Em sua ideia básica, o BIT é representado como uma array de tamanho igual ao elemento máximo mais um. Para que os elementos possam ser usados ​​como um índice.
  6. Depois disso, adicionamos o elemento atual ao BIT [] fazendo uma operação de atualização que atualiza a contagem do elemento atual de 0 a 1 e, portanto, atualiza os ancestrais do elemento atual no BIT (consulte update() no BIT para obter detalhes) . 
      
• Implementação 
   

// C++ program to count inversions using Binary Indexed Tree
#include<bits/stdc++.h>
using namespace std;
 
// Returns sum of arr[0..index]. This function assumes
// that the array is preprocessed and partial sums of
// array elements are stored in BITree[].
int getSum(int BITree[], int index)
{
    int sum = 0; // Initialize result
 
    // Traverse ancestors of BITree[index]
    while (index > 0)
    {
        // Add current element of BITree to sum
        sum += BITree[index];
 
        // Move index to parent node in getSum View
        index -= index & (-index);
    }
    return sum;
}
 
// Updates a node in Binary Index Tree (BITree) at given index
// in BITree.  The given value 'val' is added to BITree[i] and
// all of its ancestors in tree.
void updateBIT(int BITree[], int n, int index, int val)
{
    // Traverse all ancestors and add 'val'
    while (index <= n)
    {
       // Add 'val' to current node of BI Tree
       BITree[index] += val;
 
       // Update index to that of parent in update View
       index += index & (-index);
    }
}
 
// Returns inversion count arr[0..n-1]
int getInvCount(int arr[], int n)
{
    int invcount = 0; // Initialize result
 
    // Find maximum element in arr[]
    int maxElement = 0;
    for (int i=0; i<n; i++)
        if (maxElement < arr[i])
            maxElement = arr[i];
 
    // Create a BIT with size equal to maxElement+1 (Extra
    // one is used so that elements can be directly be
    // used as index)
    int BIT[maxElement+1];
    for (int i=1; i<=maxElement; i++)
        BIT[i] = 0;
 
    // Traverse all elements from right.
    for (int i=n-1; i>=0; i--)
    {
        // Get count of elements smaller than arr[i]
        invcount += getSum(BIT, arr[i]-1);
 
        // Add current element to BIT
        updateBIT(BIT, maxElement, arr[i], 1);
    }
 
    return invcount;
}
 
// Driver program
int main()
{
    int arr[] = {8, 4, 2, 1};
    int n = sizeof(arr)/sizeof(int);
    cout << "Number of inversions are : " << getInvCount(arr,n);
    return 0;
}

// Java program to count inversions
// using Binary Indexed Tree
 
class GFG
{
     
// Returns sum of arr[0..index].
// This function assumes that the
// array is preprocessed and partial
// sums of array elements are stored
// in BITree[].
static int getSum(int[] BITree, int index)
{
    int sum = 0; // Initialize result
 
    // Traverse ancestors of BITree[index]
    while (index > 0)
    {
        // Add current element of BITree to sum
        sum += BITree[index];
 
        // Move index to parent node in getSum View
        index -= index & (-index);
    }
    return sum;
}
 
// Updates a node in Binary Index
// Tree (BITree) at given index
// in BITree. The given value 'val'
// is added to BITree[i] and all
// of its ancestors in tree.
static void updateBIT(int[] BITree, int n,
                        int index, int val)
{
    // Traverse all ancestors and add 'val'
    while (index <= n)
    {
        // Add 'val' to current node of BI Tree
        BITree[index] += val;
 
        // Update index to that of parent in update View
        index += index & (-index);
    }
}
 
// Returns inversion count arr[0..n-1]
static int getInvCount(int[] arr, int n)
{
    int invcount = 0; // Initialize result
 
    // Find maximum element in arr[]
    int maxElement = 0;
    for (int i = 0; i < n; i++)
        if (maxElement < arr[i])
            maxElement = arr[i];
 
    // Create a BIT with size equal to
    // maxElement+1 (Extra one is used so
    // that elements can be directly be
    // used as index)
    int[] BIT = new int[maxElement + 1];
    for (int i = 1; i <= maxElement; i++)
        BIT[i] = 0;
 
    // Traverse all elements from right.
    for (int i = n - 1; i >= 0; i--)
    {
        // Get count of elements smaller than arr[i]
        invcount += getSum(BIT, arr[i] - 1);
 
        // Add current element to BIT
        updateBIT(BIT, maxElement, arr[i], 1);
    }
 
    return invcount;
}
 
// Driver code
public static void main (String[] args)
{
    int []arr = {8, 4, 2, 1};
    int n = arr.length;
    System.out.println("Number of inversions are : " +
                                getInvCount(arr,n));
}
}
 
// This code is contributed by mits

# Python3 program to count inversions using
# Binary Indexed Tree
 
# Returns sum of arr[0..index]. This function
# assumes that the array is preprocessed and
# partial sums of array elements are stored
# in BITree[].
def getSum( BITree, index):
    sum = 0 # Initialize result
     
    # Traverse ancestors of BITree[index]
    while (index > 0):
 
        # Add current element of BITree to sum
        sum += BITree[index]
 
        # Move index to parent node in getSum View
        index -= index & (-index)
 
    return sum
 
# Updates a node in Binary Index Tree (BITree)
# at given index in BITree. The given value
# 'val' is added to BITree[i] and all of its
# ancestors in tree.
def updateBIT(BITree, n, index, val):
 
    # Traverse all ancestors and add 'val'
    while (index <= n):
 
        # Add 'val' to current node of BI Tree
        BITree[index] += val
 
        # Update index to that of parent
        # in update View
        index += index & (-index)
 
# Returns count of inversions of size three
def getInvCount(arr, n):
 
    invcount = 0 # Initialize result
 
    # Find maximum element in arrays
    maxElement = max(arr)
 
    # Create a BIT with size equal to
    # maxElement+1 (Extra one is used
    # so that elements can be directly
    # be used as index)
    BIT = [0] * (maxElement + 1)
    for i in range(1, maxElement + 1):
        BIT[i] = 0
    for i in range(n - 1, -1, -1):
 
        invcount += getSum(BIT, arr[i] - 1)
        updateBIT(BIT, maxElement, arr[i], 1)
    return invcount
     
# Driver code
if __name__ =="__main__":
    arr = [8, 4, 2, 1]
    n = 4
    print("Inversion Count : ",
           getInvCount(arr, n))
     
# This code is contributed by
# Shubham Singh(SHUBHAMSINGH10)

// C# program to count inversions
// using Binary Indexed Tree
using System;
 
class GFG
{
     
// Returns sum of arr[0..index].
// This function assumes that the
// array is preprocessed and partial
// sums of array elements are stored
// in BITree[].
static int getSum(int []BITree, int index)
{
    int sum = 0; // Initialize result
 
    // Traverse ancestors of BITree[index]
    while (index > 0)
    {
        // Add current element of BITree to sum
        sum += BITree[index];
 
        // Move index to parent node in getSum View
        index -= index & (-index);
    }
    return sum;
}
 
// Updates a node in Binary Index
// Tree (BITree) at given index
// in BITree. The given value 'val'
// is added to BITree[i] and all
// of its ancestors in tree.
static void updateBIT(int []BITree, int n,
                        int index, int val)
{
    // Traverse all ancestors and add 'val'
    while (index <= n)
    {
        // Add 'val' to current node of BI Tree
        BITree[index] += val;
 
        // Update index to that of parent in update View
        index += index & (-index);
    }
}
 
// Returns inversion count arr[0..n-1]
static int getInvCount(int []arr, int n)
{
    int invcount = 0; // Initialize result
 
    // Find maximum element in arr[]
    int maxElement = 0;
    for (int i = 0; i < n; i++)
        if (maxElement < arr[i])
            maxElement = arr[i];
 
    // Create a BIT with size equal to
    // maxElement+1 (Extra one is used so
    // that elements can be directly be
    // used as index)
    int[] BIT = new int[maxElement + 1];
    for (int i = 1; i <= maxElement; i++)
        BIT[i] = 0;
 
    // Traverse all elements from right.
    for (int i = n - 1; i >= 0; i--)
    {
        // Get count of elements smaller than arr[i]
        invcount += getSum(BIT, arr[i] - 1);
 
        // Add current element to BIT
        updateBIT(BIT, maxElement, arr[i], 1);
    }
 
    return invcount;
}
 
// Driver code
static void Main()
{
    int []arr = {8, 4, 2, 1};
    int n = arr.Length;
    Console.WriteLine("Number of inversions are : " +
                                getInvCount(arr,n));
}
}
 
// This code is contributed by mits

<?php
// PHP program to count inversions
// using Binary Indexed Tree
 
// Returns sum of arr[0..index].
// This function assumes that the
// array is preprocessed and partial
// sums of array elements are stored
// in BITree[].
function getSum($BITree, $index)
{
    $sum = 0; // Initialize result
 
    // Traverse ancestors of BITree[index]
    while ($index > 0)
    {
        // Add current element of BITree to sum
        $sum += $BITree[$index];
 
        // Move index to parent node in getSum View
        $index -= $index & (-$index);
    }
    return $sum;
}
 
// Updates a node in Binary Index
// Tree (BITree) at given index
// in BITree. The given value 'val'
// is added to BITree[i] and
// all of its ancestors in tree.
function updateBIT(&$BITree, $n, $index,$val)
{
    // Traverse all ancestors and add 'val'
    while ($index <= $n)
    {
        // Add 'val' to current node of BI Tree
        $BITree[$index] += $val;
 
        // Update index to that of
        // parent in update View
        $index += $index & (-$index);
    }
}
 
// Returns inversion count arr[0..n-1]
function getInvCount($arr, $n)
{
    $invcount = 0; // Initialize result
 
    // Find maximum element in arr[]
    $maxElement = 0;
    for ($i=0; $i<$n; $i++)
        if ($maxElement < $arr[$i])
            $maxElement = $arr[$i];
 
    // Create a BIT with size equal
    // to maxElement+1 (Extra one is
    // used so that elements can be
    // directly be used as index)
    $BIT=array_fill(0,$maxElement+1,0);
 
    // Traverse all elements from right.
    for ($i=$n-1; $i>=0; $i--)
    {
        // Get count of elements smaller than arr[i]
        $invcount += getSum($BIT, $arr[$i]-1);
 
        // Add current element to BIT
        updateBIT($BIT, $maxElement, $arr[$i], 1);
    }
 
    return $invcount;
}
 
    // Driver program
    $arr = array(8, 4, 2, 1);
    $n = count($arr);
    print("Number of inversions are : ".getInvCount($arr,$n));
 
// This code is contributed by mits
?>

<script>
// javascript program to count inversions
// using Binary Indexed Tree  
// Returns sum of arr[0..index].
// This function assumes that the
// array is preprocessed and partial
// sums of array elements are stored
// in BITree.
function getSum(BITree , index)
{
    var sum = 0; // Initialize result
 
    // Traverse ancestors of BITree[index]
    while (index > 0)
    {
        // Add current element of BITree to sum
        sum += BITree[index];
 
        // Move index to parent node in getSum View
        index -= index & (-index);
    }
    return sum;
}
 
// Updates a node in Binary Index
// Tree (BITree) at given index
// in BITree. The given value 'val'
// is added to BITree[i] and all
// of its ancestors in tree.
function updateBIT(BITree , n, index , val)
{
    // Traverse all ancestors and add 'val'
    while (index <= n)
    {
        // Add 'val' to current node of BI Tree
        BITree[index] += val;
 
        // Update index to that of parent in update View
        index += index & (-index);
    }
}
 
// Returns inversion count arr[0..n-1]
function getInvCount(arr , n)
{
    var invcount = 0; // Initialize result
 
    // Find maximum element in arr
    var maxElement = 0;
    for (i = 0; i < n; i++)
        if (maxElement < arr[i])
            maxElement = arr[i];
 
    // Create a BIT with size equal to
    // maxElement+1 (Extra one is used so
    // that elements can be directly be
    // used as index)
    var BIT = Array.from({length: maxElement + 1}, (_, i) => 0);
    for (i = 1; i <= maxElement; i++)
        BIT[i] = 0;
 
    // Traverse all elements from right.
    for (i = n - 1; i >= 0; i--)
    {
        // Get count of elements smaller than arr[i]
        invcount += getSum(BIT, arr[i] - 1);
 
        // Add current element to BIT
        updateBIT(BIT, maxElement, arr[i], 1);
    }
 
    return invcount;
}
 
// Driver code
    var arr = [8, 4, 2, 1];
    var n = arr.length;
    document.write("Number of inversions are : " +
                                getInvCount(arr,n));
 
// This code is contributed by Amit Katiyar
</script>

• Saída:

Number of inversions are : 6

• Análise de complexidade: 
  • Complexidade de tempo: - A função de atualização e a função getSum são executadas para O (log (elemento máximo)). A função getSum deve ser executada para cada elemento da array. Portanto, a complexidade de tempo geral é: O (nlog (elemento máximo)).
  • Espaço auxiliar: O (maxElement), o espaço necessário para o BIT é uma array do tamanho do maior elemento.

Melhor solução usando BIT de tamanho Θ (n):  

• Abordagem: Percorra a array e, para cada índice, encontre o número de elementos menores em seu lado direito da array. Isso pode ser feito usando o BIT. Some as contagens de todos os índices na array e imprima a soma. A abordagem permanece a mesma, mas o problema com a abordagem anterior é que ela não funciona para números negativos, pois o índice não pode ser negativo. A ideia é converter o array fornecido em um array com valores de 1 a ne a ordem relativa dos elementos menores e maiores permanece a mesma.
  Exemplo : -

 
arr[] = {7, -90, 100, 1}

It gets  converted to,
arr[] = {3, 1, 4 ,2 }
as -90 < 1 < 7 < 100.

Explanation: Make a BIT array of a number of
elements instead of a maximum element. Changing
element will not have any change in the answer
as the greater elements remain greater and at the
same position. 

• Algoritmo: 
  1. Crie um BIT, para encontrar a contagem dos elementos menores no BIT para um determinado número e também um resultado variável = 0 .
  2. A solução anterior não funciona para arrayes contendo elementos negativos. Portanto, converta a array em uma array contendo numeração relativa de elementos, ou seja, faça uma cópia da array original e, em seguida, classifique a cópia da array e substitua os elementos na array original pelos índices dos mesmos elementos na array classificada. 
     Por exemplo, se a array for {-3, 2, 0}, a array será convertida em {1, 3, 2}
  3. Percorra a array do início ao fim.
  4. Para cada índice, verifique quantos números a menos do que o elemento atual estão presentes no BIT e adicione-o ao resultado
• Implementação: 
   

// C++ program to count inversions using Binary Indexed Tree
#include<bits/stdc++.h>
using namespace std;
 
// Returns sum of arr[0..index]. This function assumes
// that the array is preprocessed and partial sums of
// array elements are stored in BITree[].
int getSum(int BITree[], int index)
{
    int sum = 0; // Initialize result
 
    // Traverse ancestors of BITree[index]
    while (index > 0)
    {
        // Add current element of BITree to sum
        sum += BITree[index];
 
        // Move index to parent node in getSum View
        index -= index & (-index);
    }
    return sum;
}
 
// Updates a node in Binary Index Tree (BITree) at given index
// in BITree.  The given value 'val' is added to BITree[i] and
// all of its ancestors in tree.
void updateBIT(int BITree[], int n, int index, int val)
{
    // Traverse all ancestors and add 'val'
    while (index <= n)
    {
       // Add 'val' to current node of BI Tree
       BITree[index] += val;
 
       // Update index to that of parent in update View
       index += index & (-index);
    }
}
 
// Converts an array to an array with values from 1 to n
// and relative order of smaller and greater elements remains
// same.  For example, {7, -90, 100, 1} is converted to
// {3, 1, 4 ,2 }
void convert(int arr[], int n)
{
    // Create a copy of arrp[] in temp and sort the temp array
    // in increasing order
    int temp[n];
    for (int i=0; i<n; i++)
        temp[i] = arr[i];
    sort(temp, temp+n);
 
    // Traverse all array elements
    for (int i=0; i<n; i++)
    {
        // lower_bound() Returns pointer to the first element
        // greater than or equal to arr[i]
        arr[i] = lower_bound(temp, temp+n, arr[i]) - temp + 1;
    }
}
 
// Returns inversion count arr[0..n-1]
int getInvCount(int arr[], int n)
{
    int invcount = 0; // Initialize result
 
     // Convert arr[] to an array with values from 1 to n and
     // relative order of smaller and greater elements remains
     // same.  For example, {7, -90, 100, 1} is converted to
    //  {3, 1, 4 ,2 }
    convert(arr, n);
 
    // Create a BIT with size equal to maxElement+1 (Extra
    // one is used so that elements can be directly be
    // used as index)
    int BIT[n+1];
    for (int i=1; i<=n; i++)
        BIT[i] = 0;
 
    // Traverse all elements from right.
    for (int i=n-1; i>=0; i--)
    {
        // Get count of elements smaller than arr[i]
        invcount += getSum(BIT, arr[i]-1);
 
        // Add current element to BIT
        updateBIT(BIT, n, arr[i], 1);
    }
 
    return invcount;
}
 
// Driver program
int main()
{
    int arr[] = {8, 4, 2, 1};
    int n = sizeof(arr)/sizeof(int);
    cout << "Number of inversions are : " << getInvCount(arr,n);
    return 0;
}

// Java program to count inversions
// using Binary Indexed Tree
import java.util.*;
class GFG{
 
// Returns sum of arr[0..index].
// This function assumes that the
// array is preprocessed and partial
// sums of array elements are stored
// in BITree[].
static int getSum(int BITree[],
                  int index)
{
  // Initialize result
  int sum = 0;
 
  // Traverse ancestors of
  // BITree[index]
  while (index > 0)
  {
    // Add current element of
    // BITree to sum
    sum += BITree[index];
 
    // Move index to parent node
    // in getSum View
    index -= index & (-index);
  }
  return sum;
}
 
// Updates a node in Binary Index Tree
// (BITree) at given index in BITree. 
// The given value 'val' is added to
// BITree[i] and all of its ancestors
// in tree.
static void updateBIT(int BITree[], int n,
                      int index, int val)
{
  // Traverse all ancestors
  // and add 'val'
  while (index <= n)
  {
    // Add 'val' to current
    // node of BI Tree
    BITree[index] += val;
 
    // Update index to that of
    // parent in update View
    index += index & (-index);
  }
}
 
// Converts an array to an array
// with values from 1 to n and
// relative order of smaller and
// greater elements remains same. 
// For example, {7, -90, 100, 1}
// is converted to {3, 1, 4 ,2 }
static void convert(int arr[],
                    int n)
{
  // Create a copy of arrp[] in temp
  // and sort the temp array in
  // increasing order
  int []temp = new int[n];
   
  for (int i = 0; i < n; i++)
    temp[i] = arr[i];
  Arrays.sort(temp);
 
  // Traverse all array elements
  for (int i = 0; i < n; i++)
  {
    // lower_bound() Returns pointer
    // to the first element greater
    // than or equal to arr[i]
    arr[i] =lower_bound(temp,0,
                        n, arr[i]) + 1;
  }
}
 
static int lower_bound(int[] a, int low,
                       int high, int element)
{
  while(low < high)
  {
    int middle = low +
                (high - low) / 2;
    if(element > a[middle])
      low = middle + 1;
    else
      high = middle;
  }
  return low;
}
 
// Returns inversion count
// arr[0..n-1]
static int getInvCount(int arr[],
                       int n)
{
  // Initialize result
  int invcount = 0;
 
  // Convert arr[] to an array
  // with values from 1 to n and
  // relative order of smaller
  // and greater elements remains
  // same.  For example, {7, -90,
  // 100, 1} is converted to
  //  {3, 1, 4 ,2 }
  convert(arr, n);
 
  // Create a BIT with size equal
  // to maxElement+1 (Extra one is
  // used so that elements can be
  // directly be used as index)
  int []BIT = new int[n + 1];
   
  for (int i = 1; i <= n; i++)
    BIT[i] = 0;
 
  // Traverse all elements
  // from right.
  for (int i = n - 1; i >= 0; i--)
  {
    // Get count of elements
    // smaller than arr[i]
    invcount += getSum(BIT,
                       arr[i] - 1);
 
    // Add current element to BIT
    updateBIT(BIT, n, arr[i], 1);
  }
 
  return invcount;
}
 
// Driver code
public static void main(String[] args)
{
  int arr[] = {8, 4, 2, 1};
  int n = arr.length;
  System.out.print("Number of inversions are : " + 
                    getInvCount(arr, n));
}
}
 
// This code is contributed by Amit Katiyar

# Python3 program to count inversions using Binary Indexed Tree
from bisect import bisect_left as lower_bound
 
# Returns sum of arr[0..index]. This function assumes
# that the array is preprocessed and partial sums of
# array elements are stored in BITree.
def getSum(BITree, index):
 
    sum = 0 # Initialize result
 
    # Traverse ancestors of BITree[index]
    while (index > 0):
 
        # Add current element of BITree to sum
        sum += BITree[index]
 
        # Move index to parent node in getSum View
        index -= index & (-index)
 
    return sum
 
# Updates a node in Binary Index Tree (BITree) at given index
# in BITree. The given value 'val' is added to BITree[i] and
# all of its ancestors in tree.
def updateBIT(BITree, n, index, val):
 
    # Traverse all ancestors and add 'val'
    while (index <= n):
 
        # Add 'val' to current node of BI Tree
        BITree[index] += val
 
    # Update index to that of parent in update View
    index += index & (-index)
 
# Converts an array to an array with values from 1 to n
# and relative order of smaller and greater elements remains
# same. For example, 7, -90, 100, 1 is converted to
# 3, 1, 4 ,2
def convert(arr, n):
 
    # Create a copy of arrp in temp and sort the temp array
    # in increasing order
    temp = [0]*(n)
    for i in range(n):
        temp[i] = arr[i]
    temp = sorted(temp)
 
    # Traverse all array elements
    for i in range(n):
 
        # lower_bound() Returns pointer to the first element
        # greater than or equal to arr[i]
        arr[i] = lower_bound(temp, arr[i]) + 1
 
# Returns inversion count arr[0..n-1]
def getInvCount(arr, n):
 
    invcount = 0 # Initialize result
 
    # Convert arr to an array with values from 1 to n and
    # relative order of smaller and greater elements remains
    # same. For example, 7, -90, 100, 1 is converted to
    # 3, 1, 4 ,2
    convert(arr, n)
 
    # Create a BIT with size equal to maxElement+1 (Extra
    # one is used so that elements can be directly be
    # used as index)
    BIT = [0] * (n + 1)
 
    # Traverse all elements from right.
    for i in range(n - 1, -1, -1):
 
        # Get count of elements smaller than arr[i]
        invcount += getSum(BIT, arr[i] - 1)
 
        # Add current element to BIT
        updateBIT(BIT, n, arr[i], 1)
 
    return invcount
 
# Driver program
if __name__ == '__main__':
 
    arr = [8, 4, 2, 1]
    n = len(arr)
    print("Number of inversions are : ",getInvCount(arr, n))
 
# This code is contributed by mohit kumar 29

// C# program to count inversions
// using Binary Indexed Tree
using System;
class GFG{
 
// Returns sum of arr[0..index].
// This function assumes that the
// array is preprocessed and partial
// sums of array elements are stored
// in BITree[].
static int getSum(int []BITree,
                  int index)
{
  // Initialize result
  int sum = 0;
 
  // Traverse ancestors of
  // BITree[index]
  while (index > 0)
  {
    // Add current element of
    // BITree to sum
    sum += BITree[index];
 
    // Move index to parent node
    // in getSum View
    index -= index & (-index);
  }
  return sum;
}
 
// Updates a node in Binary Index Tree
// (BITree) at given index in BITree. 
// The given value 'val' is added to
// BITree[i] and all of its ancestors
// in tree.
static void updateBIT(int []BITree, int n,
                      int index, int val)
{
  // Traverse all ancestors
  // and add 'val'
  while (index <= n)
  {
    // Add 'val' to current
    // node of BI Tree
    BITree[index] += val;
 
    // Update index to that of
    // parent in update View
    index += index & (-index);
  }
}
 
// Converts an array to an array
// with values from 1 to n and
// relative order of smaller and
// greater elements remains same. 
// For example, {7, -90, 100, 1}
// is converted to {3, 1, 4 ,2 }
static void convert(int []arr,
                    int n)
{
  // Create a copy of arrp[] in temp
  // and sort the temp array in
  // increasing order
  int []temp = new int[n];
   
  for (int i = 0; i < n; i++)
    temp[i] = arr[i];
  Array.Sort(temp);
 
  // Traverse all array elements
  for (int i = 0; i < n; i++)
  {
    // lower_bound() Returns pointer
    // to the first element greater
    // than or equal to arr[i]
    arr[i] =lower_bound(temp,0,
                        n, arr[i]) + 1;
  }
}
 
static int lower_bound(int[] a, int low,
                       int high, int element)
{
  while(low < high)
  {
    int middle = low +
                (high - low) / 2;
    if(element > a[middle])
      low = middle + 1;
    else
      high = middle;
  }
  return low;
}
 
// Returns inversion count
// arr[0..n-1]
static int getInvCount(int []arr,
                       int n)
{
  // Initialize result
  int invcount = 0;
 
  // Convert []arr to an array
  // with values from 1 to n and
  // relative order of smaller
  // and greater elements remains
  // same.  For example, {7, -90,
  // 100, 1} is converted to
  //  {3, 1, 4 ,2 }
  convert(arr, n);
 
  // Create a BIT with size equal
  // to maxElement+1 (Extra one is
  // used so that elements can be
  // directly be used as index)
  int []BIT = new int[n + 1];
   
  for (int i = 1; i <= n; i++)
    BIT[i] = 0;
 
  // Traverse all elements
  // from right.
  for (int i = n - 1; i >= 0; i--)
  {
    // Get count of elements
    // smaller than arr[i]
    invcount += getSum(BIT,
                       arr[i] - 1);
 
    // Add current element
    // to BIT
    updateBIT(BIT, n,
              arr[i], 1);
  }
 
  return invcount;
}
 
// Driver code
public static void Main(String[] args)
{
  int []arr = {8, 4, 2, 1};
  int n = arr.Length;
  Console.Write("Number of inversions are : " + 
                 getInvCount(arr, n));
}
}
 
// This code is contributed by Amit Katiyar

<script>
// Javascript program to count inversions
// using Binary Indexed Tree
     
// Returns sum of arr[0..index].
// This function assumes that the
// array is preprocessed and partial
// sums of array elements are stored
// in BITree[].   
function getSum(BITree,index)
{
 
        // Initialize result
  let sum = 0;
  
  // Traverse ancestors of
  // BITree[index]
  while (index > 0)
  {
   
    // Add current element of
    // BITree to sum
    sum += BITree[index];
  
    // Move index to parent node
    // in getSum View
    index -= index & (-index);
  }
  return sum;
}
 
// Updates a node in Binary Index Tree
// (BITree) at given index in BITree.
// The given value 'val' is added to
// BITree[i] and all of its ancestors
// in tree.
function updateBIT(BITree,n,index,val)
{
 
    // Traverse all ancestors
  // and add 'val'
  while (index <= n)
  {
   
    // Add 'val' to current
    // node of BI Tree
    BITree[index] += val;
  
    // Update index to that of
    // parent in update View
    index += index & (-index);
  }
}
 
// Converts an array to an array
// with values from 1 to n and
// relative order of smaller and
// greater elements remains same.
// For example, {7, -90, 100, 1}
// is converted to {3, 1, 4 ,2 }
function convert(arr, n)
{
 
    // Create a copy of arrp[] in temp
  // and sort the temp array in
  // increasing order
  let temp = new Array(n);
    
  for (let i = 0; i < n; i++)
    temp[i] = arr[i];
  temp.sort(function(a, b){return a - b;});
  
  // Traverse all array elements
  for (let i = 0; i < n; i++)
  {
    // lower_bound() Returns pointer
    // to the first element greater
    // than or equal to arr[i]
    arr[i] =lower_bound(temp,0,
                        n, arr[i]) + 1;
  }
}
 
function lower_bound(a,low,high,element)
{
    while(low < high)
  {
    let middle = low +
                Math.floor((high - low) / 2);
    if(element > a[middle])
      low = middle + 1;
    else
      high = middle;
  }
  return low;
}
 
// Returns inversion count
// arr[0..n-1]
function getInvCount(arr,n)
{
    // Initialize result
  let invcount = 0;
  
  // Convert arr[] to an array
  // with values from 1 to n and
  // relative order of smaller
  // and greater elements remains
  // same.  For example, {7, -90,
  // 100, 1} is converted to
  //  {3, 1, 4 ,2 }
  convert(arr, n);
  
  // Create a BIT with size equal
  // to maxElement+1 (Extra one is
  // used so that elements can be
  // directly be used as index)
  let BIT = new Array(n + 1);
    
  for (let i = 1; i <= n; i++)
    BIT[i] = 0;
  
  // Traverse all elements
  // from right.
  for (let i = n - 1; i >= 0; i--)
  {
    // Get count of elements
    // smaller than arr[i]
    invcount += getSum(BIT,
                       arr[i] - 1);
  
    // Add current element to BIT
    updateBIT(BIT, n, arr[i], 1);
  }
  
  return invcount;
}
 
// Driver code
let arr=[8, 4, 2, 1];
let n = arr.length;
document.write("Number of inversions are : " +
                    getInvCount(arr, n));
 
    // This code is contributed by unknown2108
</script>

• Saída:

Number of inversions are : 6

• Análise de complexidade: 
  • Complexidade de tempo: a função de atualização e a função getSum são executadas para O (log (n)). A função getSum deve ser executada para cada elemento da array. Portanto, a complexidade de tempo geral é O (nlog (n)).
  • Espaço auxiliar: O (n). 
    O espaço necessário para o BIT é uma array de tamanho n.

Este artigo é uma contribuição de Abhiraj Smit. Escreva comentários se encontrar algo incorreto ou se quiser compartilhar mais informações sobre o tópico discutido acima.