315. Count of Smaller Numbers After Self

对每个元素找它后面比它小的元素个数。找前面或后面比它大/小元素的题可以用BST或Binary Index Tree做。BIT能以O(lgN)时间query（含）指定index前所有元素的和，并且能任意更改元素的值而不影响查询区域和的时间，具体实现比较tricky, 可以参考花花的视频。利用BIT的性质，要O(lg(N))时间查出一个和，这个和直接就是个数。因此BIT相当于在统计频率, index对应成（唯一）元素值，每个index存的值就是针对这个值的个数。所以先统计出所有可能的元素的值，排序并根据值分配它在BIT里的index，这样一次query就能把值小于它的全部统计出来。因为要统计后面的，所以从后往前遍历。

/*
 * @lc app=leetcode id=315 lang=cpp
 *
 * [315] Count of Smaller Numbers After Self
 *
 * https://leetcode.com/problems/count-of-smaller-numbers-after-self/description/
 *
 * algorithms
 * Hard (39.01%)
 * Likes:    1364
 * Dislikes: 62
 * Total Accepted:    87.5K
 * Total Submissions: 223.1K
 * Testcase Example:  '[5,2,6,1]'
 *
 * 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:
 * 
 * 
 * Input: [5,2,6,1]
 * Output: [2,1,1,0] 
 * Explanation:
 * 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.
 * 
 */
class BIT {
public: 
    BIT(const int N): sums(N + 1, 0) {}

    void update(int i, int delta) {
        while (i < sums.size()) {
            sums[i] += delta;
            i += lowbit(i); 
        }
    }

    int query(int i) const {
        int sum = 0;
        while (i > 0) {
            sum += sums[i];
            i -= lowbit(i);
        }
        return sum;
    }
    static inline int lowbit(int x) {return x & (-x);}
    vector<int> sums;
};

class Solution {
public:
    vector<int> countSmaller(vector<int>& nums) {
        // sort the unique numbers
        set<int> sorted(nums.begin(), nums.end());
        // map the number to the BIT index.
        unordered_map<int, int> indices;
        int index = 0;
        // 小于等于num的个数
        for (const int num : sorted) indices[num] = ++index;
        vector<int> res;
        // tree的index是rank, val/sums[i]是rank<=i的count。
        BIT tree(indices.size());
        for (int i = nums.size() - 1; i >= 0; --i) {
            // 找出有多少个数 < num_i
            res.push_back(tree.query(indices[nums[i]] - 1));
            // 把num_i所代表的index的count + 1
            tree.update(indices[nums[i]], 1);
        }
        reverse(res.begin(), res.end());
        return res;
    }
};