题意：给定一个整数数组 nums，按要求返回一个新数组 counts。数组 counts 有该性质： counts[i] 的值是 nums[i] 右侧小于 nums[i] 的元素的数量。
思路：这题有很多做法，一种是从后往前扫，每次将数字加入到一个二叉搜索树中去，查找比当前节点小的节点数量即可。要维护二叉搜索树有点烦。另外一种方法是使用树状数组或者线段树。将nums数组离散化到1-N。倒序扫描离散化后的数组，每次首先查找区间0-nums[i]的和，然后将nums[i]位置加1。这里可以使用树状数组，比较好写。
复杂度：O(N*logN)
C++代码：
class Solution {
public:
typedef long long LL;
static const int MAXN = 100010;
int tree[MAXN];
int lowbit(int x){
return x & (-x);
}
void add(int i, int val){
while(i < MAXN){
tree[i] += val;
i += lowbit(i);
}
}
int sum(int i){
int s = 0;
while(i > 0){
s += tree[i];
i -= lowbit(i);
}
return s;
}
vector<int> countSmaller(vector<int>& nums) {
vector<int> res;
if(nums.size() == 0) return res;
memset(tree, 0, sizeof(tree));
vector<int> a = nums;
sort(nums.begin(), nums.end());
unique(nums.begin(), nums.end());
for(int i = 0; i < a.size(); i++){
a[i] = lower_bound(nums.begin(), nums.end(), a[i]) - nums.begin() + 1;
}
for(int i = a.size() - 1; i >= 0; i--){
res.push_back(sum(a[i] - 1));
add(a[i], 1);
}
reverse(res.begin(), res.end());
return res;
}
};
