Complexity of algorithm to find number of elements > element index i in an array
Your problem is very related to that of computing the number of inversions in a permutation, or (equivalently) the Kendall tau distance between two permutations; this is the sum of your vector. In fact, your vector (with a very superficial change in the definition) is known as the inversion vector.

There is a classical data structure of Dietz that can be used to compute the inversion vector in time $O(n\log n/\log\log n)$; the $O(n\log n)$ solution you mention is the baseline here. Fredman and Saks proved a matching lower bound showing that the time complexity of Dietz's data structure is optimal. Computing the insertion vector can however be done faster: Chan and Pătraşcu give an $O(n\sqrt{\log n})$ algorithm (see under "Offline dynamic ranking and selection").