given an array, for each element, find out the total number of elements lesser than it, which appear to the right of it

It can be solved in O(n log n).

If in a BST you store the number of elements of the subtree rooted at that node when you search the node (reaching that from the root) you can count number of elements larger/smaller than that in the path:

int count_larger(node *T, int key, int current_larger){
    if (*T == nil)
        return -1;
    if (T->key == key)
        return current_larger + (T->right_child->size);
    if (T->key > key)
        return count_larger(T->left_child, key, current_larger + (T->right_child->size) + 1);
    return count_larger(T->right_child, key, current_larger)
}

** for example if this is our tree and we're searching for key 3, count_larger will be called for:

-> (node 2, 3, 0)
--> (node 4, 3, 0)
---> (node 3, 3, 2)

and the final answer would be 2 as expected.

Suppose the Array is 6,-1,5,10,12,4,1,3,7,50

Steps

1.We start building a BST from right end of the array.Since we are concerned with all the elements to right for any element.

2.Suppose we have formed the partial solution tree upto the 10.

3.Now when inserting 5 we do a tree traversal and insert to the right of 4. Notice that each time we traverse to the right of any node we increment by 1 and add the no. of elements in left subtree of that node. eg:
for 50 it is 0
for 7 it is 0
for 12 it is 1 right traversel + leftsubtree size of 7 = 1+3 =4
for 10 same as above.
for 4 it is 1+1 =2

While building bst we can easily maintain the left subtree size for each node by simply maintaining a variable corresponding to it and incrementing it by 1 each time a node traverses to the left by it.
Hence the Solution Average case O(nlogn).

We can use other optimizations such as predetermining whether array is sorted in decreasing order find groups of element in decreasing order treat them as single.

I think is it possible to do it in O(nlog(n))with a modified version of quicksort. Basically each time you add an element to less, you check if this element rank in the original array was superior to the rank of the current pivot. It may look like

oldrank -> original positions 
count -> what you want
function quicksort('array')
  if length('array') ≤ 1
      return 'array'  // an array of zero or one elements is already sorted
  select and remove a pivot value 'pivot' from 'array'
  create empty lists 'less' and 'greater'
  for each 'x' in 'array'
      if 'x' ≤ 'pivot' 
         append 'x' to 'less'
         if oldrank(x) > = oldrank(pivot)  increment count(pivot)
      else 
         append 'x' to 'greater'
         if oldrank(x) <  oldrank(pivot)  increment count(x) //This was missing
  return concatenate(quicksort('less'), 'pivot', quicksort('greater')) // two recursive calls

EDIT:

Actually it can be done using any comparison based sorting algorithm . Every time you compare two elements such that the relative ordering between the two will change, you increment the counter of the bigger element.

Original pseudo-code in wikipedia.