Clean C++ solution using binary indexed tree


  • 0
    B
    class Solution {
    public:
    vector<int> bitree;
    
    int bit(int x){
        return x & -x;
    }
    
    void insert(int u, int v, int n){
        for(int i = u; i <= n; i += bit(i)){
            bitree[i] += v;
        }    
    }
    
    int get(int x){
        int ret = 0;
        for(int i = x; i > 0; i -= bit(i)){
            ret += bitree[i];
        }
        return ret;
    }
    
    vector<int> countSmaller(vector<int>& nums) {
        set<int> aux(nums.begin(), nums.end());
        vector<int> vec(aux.begin(), aux.end());
        int n = vec.size();
        bitree.assign(n+1, 0);
        map<int, int> m;
        for(int i = 1; i <= n; i ++){
            m[vec[i-1]] = i;
        }
        
        vector<int> ret;
        int sz = nums.size();
        for(int i = sz - 1; i >= 0; i --){
            insert(m[nums[i]], 1, n);
            ret.push_back(get(m[nums[i]]-1));
        }
        reverse(ret.begin(), ret.end());
        return ret;
    }
    

    };


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.