315. Count of Smaller Numbers After Self

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

• new solution update 2022.02.18

class Solution {
    vector<int> fenwickTree;
    int append = 10001;
    void update(int idx, int v) {
        while(idx < fenwickTree.size()) {
            fenwickTree[idx] += v;
            idx = idx + (idx & -idx);
        }
    }
    int sum(int idx) {
        int res = 0;
        while(idx > 0) {
            res += fenwickTree[idx];
            idx = idx - (idx & -idx);
        }
        return res;
    }
public:
    vector<int> countSmaller(vector<int>& nums) {
        fenwickTree = vector<int>(20003, 0);
        vector<int> res(nums.size(), 0);
        for(int i = 1; i < nums.size(); i++) {
            update(nums[i] + append,1);
        }
        
        for(int i = 0; i < nums.size() - 1; i++) {
            res[i] = sum(nums[i] + append-1);
            update(nums[i+1] + append, -1);
        }
        return res;
    }
};

class Solution {
    void mergeSort(vector<pair<int,int>>::iterator l, vector<pair<int,int>>::iterator r, vector<int>& res) {
        if(r <= 1 + l) return;
        vector<pair<int,int>>::iterator m =  l + (r - l) / 2;
        mergeSort(l, m, res);
        mergeSort(m, r, res);
        for(auto i = l, j = m; i < m; i++) {
            while(j < r && i->first > j->first) j++;
            res[i->second] += j - m;
        }
        inplace_merge(l, m, r);
    }
public:
    vector<int> countSmaller(vector<int>& nums) {
        vector<pair<int, int>> num(nums.size());
        vector<int> res(nums.size());
        for(int i = 0; i < nums.size(); i++) num[i] = {nums[i], i};
        mergeSort(num.begin(), num.end(), res);
        return res;
    }
};

class SegmentTree {
    int min, max, count;
    SegmentTree *left, *right;
    inline int _getFromChild(int n) {
        int res = 0;
        if(left) res += left->get(n);
        if(right) res += right->get(n);
        return res;
    }

    int _mid() {
        return min + (max + 1 - min) / 2;
    }

public:
    SegmentTree(int min, int max) : min(min), max(max), count(0), left(nullptr), right(nullptr) {};

    int get(int n) {
        return n >= max ? count : n < min ? 0 : _getFromChild(n);
    }

    void add(int n) {
        count++;
        if(min == max) return;
        if(_mid() > n) {
            if(!left) left = new SegmentTree(min, _mid() - 1);
            left->add(n);
        } else {
            if(!right) right = new SegmentTree(_mid(), max);
            right->add(n);
        }
    }
};
class Solution {
public:
    vector<int> countSmaller(vector<int>& nums) {
        vector<int> res(nums.size());
        SegmentTree* tree = new SegmentTree(*min_element(nums.begin(), nums.end()), *max_element(nums.begin(), nums.end()));

        for(int i = nums.size() - 1; i >= 0; i--) {
            res[i] = tree->get(nums[i] - 1);
            tree->add(nums[i]);
        }

        return res;
    }
};