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

Question

I had previously posted a question, Given an array, find out the next smaller element for each element now, i was trying to know , if there is any way to find out "given an array, for each element, find out the total number of elements lesser than it, which appear to the right of it" for example, the array [4 2 1 5 3] should yield [3 1 0 1 0]??

[EDIT] I have worked out a solution, please have a look at it, and let me know if there is any mistake.

1 Make a balanced BST inserting elements traversing the array from right to left

2 The BST is made in such a way that each element holds the size of the tree rooted at that element

3 Now while you search for the right position to insert any element, take account of the total size of the subtree rooted at left sibling + 1(for parent) if you move right Now since, the count is being calculated at the time of insertion of an element, and that we are moving from right to left, we get the exact count of elements lesser than the given element appearing after it.

Answer 1

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.

Answer 2

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.