对每个元素找它后面比它小的元素个数。找前面或后面比它大/小元素的题可以用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;
}
};