315

class Solution {
public:
    vector<int> bit;
    void update(int idx, int val){
        while(idx < 20004){
            bit[idx] += val;
            idx += (idx & -idx);
        }
    }

    int query(int idx){
        int sum = 0;
        while(idx > 0){
            sum += bit[idx];
            idx -= (idx & -idx);
        }
        return sum;
    }

    vector<int> countSmaller(vector<int>& nums) {
        vector<int> res;
        bit.resize(20004, 0);
        for(int i=nums.size()-1; i>=0; i--){
            int num = nums[i] + 10001;
            res.push_back(query(num-1));
            update(num, 1);
        }
        reverse(res.begin(), res.end());
        return res;
    }
};