这道题好难，考察树状数组。 思路：首先，先判断nums是否为0数组，若是做出相应选择；然后将nums转化为从1开始的数组，即整体平移，使其最小值为1；然后构造树状数组tree，tree【i】的含义要搞清楚：从tree【i】加到i去尾到0的tree【0】为，当前数字num位置后面的， 比num小的数的个数之和。然后每移动一次要更新一次tree。
C++ 代码：
class Solution { public: vector<int> countSmaller(vector<int>& nums) { vector<int> ret; int min1 = INT_MAX, max1 = INT_MIN; int len = nums.size(); if (len == 0 ) return ret; for (auto i : nums) { min1 = min(min1, i); } for (int i=0; i<len; i++) { nums[i] = nums[i] - min1 + 1; max1 = max(max1, nums[i]); } int *tree = new int[max1+1]; memset(tree, 0, sizeof(int)*(max1+1)); for (int i=len -1; i>=0; i--) { add(ret, nums[i] - 1, tree); update(tree, nums[i], max1 + 1); } free(tree); return ret; } void add(vector<int> &ret, int num, int *tree) { int sum = 0; while (num > 0) { sum += tree[num]; num -= (num&(-num)); } ret.insert(ret.begin(), sum); } void update(int *tree, int num, int maxsize) { while (num < maxsize) { tree[num]++; num += num&(-num); } } };