Count of Smaller Numbers After Self -- LeetCode

[Question]

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].

[Analysis]
This is typical problem for Binary Index Tree. Binary Index Tree is a way to update and count an array by the steps of 2^x. The time complexity of update and count is O(LogN).

To get the number smaller than and to the right of nums[i], we need to know the position of each nums[i] when sorted. Then we go through nums[] from right to left, place the value nums[i] one by one in Binary Index Tree, in the position of sorted array (sorted_pos[nums[i]]). At the same time, we count how many of smaller nums[i] has been placed, then we got the result. The overall time complexity is O(NLogN).

There is a similar problem in LintCode "Reverse Order": For an array A, if i < j, and A [i] > A [j], called (A [i], A [j]) is a reverse pair.  return total of reverse pairs in A. The solution is also provided below.

Another solution is to use Binary Search Tree. The code is simple but the catch is the std::distance() operates linearly on multiset. That makes the overall time complexity O(N^2) -- need self-made multiset instead.

    vector<int> countSmaller(vector<int>& nums) {
        vector<int> res;
        multiset<int> mset;
     
        mset.insert(INT_MAX);
        for (int i=nums.size()-1; i>=0; i--) {
            int dist = distance(mset.begin(), mset.lower_bound(nums[i]) );
            res.push_back(dist);
            mset.insert(nums[i]);
        }
        reverse(res.begin(), res.end());
        return res;
    }

Update: A clean BST based solution is attached at the bottom.

Update: A Merge Sort based solution is attached at the bottom.

[Solution] 
//--Count Smaller--
class BITree {
    vector<int> nodes;
    int lowbit(int x) { return x&(-x); };
public:
    BITree(int n): nodes(n+1, 0) {};
 
    void add (int i, int val) {
        while (i<nodes.size()) {
            nodes[i] += val;
            i += lowbit(i);
        }
    }
 
    int sum(int i) {
        int sum = 0;
        while (i>0) {
            sum += nodes[i];
            i -= lowbit(i);
        }
        return sum;
    }
};

class Solution {
public:
    vector<int> countSmaller(vector<int>& nums) {
        vector<int> sorted (nums);
        sort(sorted.begin(), sorted.end());
     
        unordered_map<int, int> map;
        for (int i=0; i<sorted.size(); i++ ) {
            map[ sorted[i] ] = i+1;
        }
     
        BITree tree(sorted.size());
        vector<int> rslt(nums.size(), 0);
        for (int i= nums.size()-1; i>=0; i--) {
            rslt[i] = tree.sum( map[nums[i]]-1 );
            tree.add( map[nums[i]], 1 );
        }
        return rslt;
    }
};
 
//--Reverse Orders (lintcode) --
class Solution {
public:
    long long reversePairs(vector<int>& A) {
        if (A.size()==0||A.size()==1) return 0;
       
        vector<int> B(A);
        sort(B.begin(), B.end());
        map<int, int> map;
        for(int i=0; i<B.size(); i++) map[B[i]] =i+1;
       
        BITree tree(B.size());
        int ret=0;
        for(int i=A.size()-1; i>=0; i--) {
            ret+= tree.sum(map[A[i]]-1);
            tree.add(map[A[i]], 1);
        }
        return ret;
    }
};


//-- BST based solution --
class Solution {
public:
    struct Node {
        int val, smaller;
        Node *left, *right;
        Node(int v, int s) : val(v), smaller(s), left(NULL), right(NULL) {}
    };
 
    int insert_node(Node*& root, int val) {
        if (root==NULL)
            return (root=new Node(val, 0)), 0;

        if (val < root->val)
            return root->smaller++, insert_node(root->left, val);
        else
            return insert_node(root->right, val)+ root->smaller+ (val>root->val?1:0);
    }
 
    vector<int> countSmaller(vector<int>& nums) {
        Node *root=NULL;
        deque<int> res;
        for (int i=nums.size()-1; i>=0; i--)
            res.push_front( insert_node(root, nums[i]) );
     
        return vector<int>(res.begin(), res.end());
    }
};

//-- Based on Merge Sort ---
class Solution {
        void mcount(vector<pair<int,int>>&pairs, int lo, int hi, vector<int>&res){
            if (hi==lo+1) return;
            int mid = (hi+lo)/2;
           
            mcount(pairs, lo, mid, res);
            mcount(pairs, mid, hi, res);
           
            //-- merger sort and count.
            vector<pair<int,int>> tmp;
            int i=lo, j=mid;
            while (i<mid && j<hi)
                if (pairs[i].first <= pairs[j].first) {
                    res[pairs[i].second]+= j-mid;
                    tmp.push_back(pairs[i++]);
                }
                else tmp.push_back(pairs[j++]);
            while(i<mid) {
                    res[pairs[i].second]+= j-mid;
                    tmp.push_back(pairs[i++]);
            }
            while (j<hi) tmp.push_back(pairs[j++]);
            for (auto& n:tmp) pairs[lo++] = n;
        };
public:
    vector<int> countSmaller(vector<int>& nums) {
        if (nums.empty()) return {};
        vector<int> res(nums.size(), 0);
       
        //-- need to memorize the orignal index of each number
        vector<pair<int,int>> pairs;
        for (int i=0; i<nums.size(); i++)
            pairs.push_back({nums[i], i});
       
        mcount (pairs, 0, pairs.size(), res);
        return res;
    }
};