You are given an integer array nums and you have to return a new counts array. The counts array has the property where counts[i] is the number of smaller elements to the right of nums[i].

Example:

Given nums = [5, 2, 6, 1]

To the right of 5 there are 2 smaller elements (2 and 1).
To the right of 2 there is only 1 smaller element (1).
To the right of 6 there is 1 smaller element (1).
To the right of 1 there is 0 smaller element.
Return the array [2, 1, 1, 0].

Solution 1(divide and conquer):

vector<int> countSmaller(vector<int>& nums) {
        int n = nums.size();
        vector<int> cnt(n, 0);
        vector<int> index(n);
        for(int i = 0; i<n; i++)
            index[i] = i;
        mergeSort(nums, cnt, index, 0, n-1);
        return cnt;
    }
    void mergeSort(vector<int>& nums, vector<int>& cnt, vector<int>& index, int left, int right) {
        if(left >= right) return;
        int mid = (left + right)/2;
        mergeSort(nums, cnt, index, left, mid);
        mergeSort(nums, cnt, index, mid+1, right);
        merge(nums, cnt, index, left, right);
    }
    void merge(vector<int>& nums, vector<int>& cnt, vector<int>& index, int left, int right) {
        int mid = (left+right)/2;
        int i = left, j = mid+1, k = 0, count = 0;
        vector<int> newindex(right-left+1);
        while(i<=mid || j<=right){
            if(i>mid)
                newindex[k++] = index[j++];
            else if(j>right){
                cnt[index[i]] += count;
                newindex[k++] = index[i++];
            }
            else if(nums[index[i]] <= nums[index[j]]){
                cnt[index[i]] += count;
                newindex[k++] = index[i++];
            }
            else{
                newindex[k++] = index[j++];
                count++;
            }
        }
        for(i = 0; i<=right-left; i++)
            index[left+i] = newindex[i];
    }

notes:
Should change the index instead of the array itself.
reference:
https://leetcode.com/problems/count-of-smaller-numbers-after-self/discuss/76583/11ms-JAVA-solution-using-merge-sort-with-explanation

Solution 2(augmented BST):

class TreeNode{
    public:
        TreeNode *left = NULL, *right = NULL;
        int val, sum, dup = 1;
        TreeNode(int val){
            this->val = val;
            this->sum = 0;
        }
    };
    vector<int> countSmaller(vector<int>& nums) {
        int n = nums.size();
        vector<int> ans(n, 0);
        TreeNode* root = NULL;
        for(int i = n-1; i>=0; i--)
            root = insert(nums[i], ans, root, i, 0);
        return ans;
    }
    TreeNode* insert(int num, vector<int>& ans, TreeNode* root, int i, int preSum) {
        if(root == NULL){
            root = new TreeNode(num);
            ans[i] = preSum;
        }
        else if(num == root->val){
            root->dup++;
            ans[i] = preSum + root->sum;
        }
        else if(num < root->val){
            root->sum++;
            root->left = insert(num, ans, root->left, i, preSum);
        }
        else{
            root->right = insert(num, ans, root->right, i, preSum + root->sum + root->dup);
        }
        return root;
    }

reference:
https://leetcode.com/problems/count-of-smaller-numbers-after-self/discuss/76580/9ms-short-Java-BST-solution-get-answer-when-building-BST