315. Count of Smaller Numbers After Self(Hard)

题目要求出所有元素的其右边比它小的元素个数。

我的解法：

1.先对数组进行排序，然后采用树状数组记录比当前元素出现次数少的元素的个数。如5，4，7，2，排序后为2，4，5，7，那么树状数组记录了0（比2小的元素个数），1（比4小的元素个数），2（比5小的元素个数），3（比7小的元素个数）。

2.查询的时候查询比元素nums[i]小的元素出现次数总和，查询当前元素时，对当前元素的出现次数进行-1操作（同时会更新树状数组），表示当前元素出现在后面元素的前面，后面的元素统计时不应该把这个元素的数量计算进去。

3.按照nums的次序进行查询，这样可以确保已经查询过的元素（即在当前元素左边的元素）在树状数组里面的出现次数也相应减少了，所以可以放心查询比nums[i]元素小的元素个数。

4.排序使用了set，时间复杂度为O（nlogn），后面树状数组查询操作时间复杂度为O(nlogn)。

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:

Given nums = [5, 2, 6, 1]

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.

Return the array [2, 1, 1, 0].

AC代码：

class Solution {
public:
	vector<int> tree;
	//树状数组函数：
	int lowbit(int x)
	{
		return (x&-x);
	}

	void add(int x, int val)
	{
		for (int i = x; i<tree.size(); i += lowbit(i))
			tree[i] += val;
	}

	int get(int x)
	{
		int sum = 0;
		for (int i = x; i; i -= lowbit(i))
			sum += tree[i];
		return sum;
	}

	vector<int> countSmaller(vector<int>& nums) {

		set<int> sortNumsSet;
		map<int, int> times;

		//对nums进行排序和统计
		for (int i = 0; i<nums.size(); i++)
		{
			times[nums[i]]++;
			sortNumsSet.insert(nums[i]);
		}
		//建立树状数组
		tree = vector<int>(sortNumsSet.size() + 1, 0);

		map<int, int> pos;
		vector<int> sortNums(sortNumsSet.size(), 0);
		set<int>::iterator ite = sortNumsSet.begin();
		//复制到新的数组中，并且记录元素的位置。
		for (int i = 0; i<sortNums.size(); i++)
		{
			sortNums[i] = *ite;
			pos[sortNums[i]] = i + 1;
			ite++;
			add(i + 1, times[sortNums[i]]);
		}

		vector<int> ans(nums.size(), 0);
		for (int i = 0; i<nums.size(); i++)
		{
			//当前元素的出现次数－1
			add(pos[nums[i]], -1);
			//获取nums[i]前面的元素总数
			ans[i] = get(pos[nums[i]] - 1);
			//cout<<ans[i]<<' ';
		}

		return ans;

	}
};