Prerequisites: AVL Trees
Problem
Given an array A of size n. Print the inversion count of that array. Assume all the elements in the array are unique.
Input:
 An integer n.
 The next n lines contain the array elements.
Output: Print the inversion count of that array.
Inversion count for an array indicates how far (or close) it is from being sorted.
There is an inversion in an array A if A[i] > A[j] and i < j.
 The inversion count is minimum, i.e., 0, if the array is sorted in increasing order.
 The inversion count is maximum, i.e., (n*(n1))/2, when an array is sorted in decreasing order where n is the size of the array.
Example,
1. Input: N = 5, A[] = {5, 4, 6, 7, 1} Output: 5 Explanation: Array A has five inversions: (5,4), (5,1), (4,1), (6,1), (7,1).
2. Input: N = 6, A[] = {6, 5, 4, 3, 2} Output: 10 Explanation: Array A has ten inversions: (6,5), (6,4), (6,3), (6,2), (5,4), (5,3), (5,2), (4,3), (4,2), (3,2).
3. Input: A[] = {1, 2, 3, 4, 6, 8} Output: 0 Explanation: Array A has 0 inversions. 
Alert Ninjas: Don’t stop now! Enroll in the Competitive Programming course today. Learn the art of writing time and spaceefficient code and compete in code competitions worldwide.
Recommended: Try to solve it yourself before moving on to the solution.
Solution
Idea: The idea is to use a SelfBalancing Binary Search Tree, such as the RedBlack Tree or the AVL Tree, and augment it so that each node keeps track of the number of nodes in the right subtree.
Algorithm:
 Start with an empty AVL tree. The tree has a property that every node stores the size of the subtree rooted with this node.
 Initialize a variable result or count as 0.

Iterate from array index 0 to n1, and for every element in A[i], do the following:
 Insert A[i] in the AVL tree.
 When we insert A[i], elements from A[0] to A[i1] are already in the AVL Tree.
 For insertion into the AVL Tree, traverse from root to a leaf by comparing every node with A[i]. If A[i] is smaller than the current node, increase the inversion count by 1+ the number of nodes in the right subtree of the current node (which is the count of all the greater elements on the left of A[i]).
 Return the count.
C++
#include<bits/stdc++.h> using namespace std; struct Node { struct Node *left, *right; int key, height; // size of the subtree from this node. int size; }; struct Node* newNode(int key) { struct Node* newNode = new Node; newNode>key = key; newNode>left = NULL; newNode>right = NULL; newNode>height = 1; newNode>size = 1; return newNode; } // A function to get the tree's height rooted at the node. int height(struct Node *node) { if (!node) return 0; return node>height; } // A function to get the size of the tree rooted at the node. int size(struct Node *node) { if (!node) return 0; return node>size; } // A function to right rotate the subtree rooted at the node. struct Node *rightRotate(struct Node *node) { struct Node *x = node>left; struct Node *y = x>right; // Perform the rotation. x>right = node; node>left = y; // Update the heights. node>height = max(height(node>right), height(node>left))+1; x>height = max(height(x>right) , height(x>left))+1; // Update the sizes. node>size = 1 + size(node>left) + size(node>right); x>size = 1 + size(x>left) + size(x>right); // Return the new root. return x; } // A function to left rotate the subtree rooted at node. struct Node *leftRotate(struct Node *node) { struct Node *x = node>right; struct Node *y = x>left; // Perform the rotation. x>left = node; node>right = y; // Update the heights. node>height = max(height(node>right), height(node>left))+1; x>height = max(height(x>right) , height(x>left))+1; // Update the sizes. node>size = 1 + size(node>left) + size(node>right); x>size = 1 + size(x>left) + size(x>right); // Return the new root. return x; } // Get the Balance factor of Node N. int getBalance(struct Node *node) { if (!node) return 0; return height(node>left)  height(node>right); } // Insert function for the insertions in AVL tree. struct Node* insert(struct Node* node, int key, int &count) { if (!node) return(newNode(key)); if (key < node>key) { node>left = insert(node>left, key, count); count += + size(node>right) + 1; } else node>right = insert(node>right, key, count); // Update the height and the size of the ancestor nodes. node>height = max(height(node>left), height(node>right)) + 1; node>size = size(node>left) + size(node>right) + 1; int balance = getBalance(node); // Left Left. if (balance > 1 && key < node>left>key) return rightRotate(node); // Right Right. if (balance < 1 && key > node>right>key) return leftRotate(node); // Right Left. if (balance < 1 && key < node>right>key) { node>right = rightRotate(node>right); return leftRotate(node); } // Left Right. if (balance > 1 && key > node>left>key) { node>left = leftRotate(node>left); return rightRotate(node); } return node; } // The function for inversion count. int getInversions(int A[], int n) { // Create an empty AVL Tree. struct Node *root = NULL; int count = 0; for (int i=0; i <= n1 ; i++) root = insert(root, A[i], count); return count; } int main() { int n = 5; int A[] = {5, 4, 6, 7, 1}; cout << "Number of inversions count in the array are : " << getInversions(A,n); return 0; } 
Input: A[] = {5, 4, 6, 7, 1}
Output:
Time complexity: O(n*logn). Because there are n elements and insertion in an AVL tree takes O(logn) time, the time complexity becomes O(n*log n).
Space Complexity: O(n). Since an AVL tree was created here with max ‘n’ nodes, hence, O(n) extra space is required here.
Check out this problem  Count Inversions.