[LeetCode]Count of Range Sum

range sum的问题通常很多时候都要转化成presum的问题，这道题也是类似的，我们计算出原array的presum array，之后我们就可以把题目转化为求对于给定的上下界，lower和upper，找出满足条件的reverse pair nums[i], nums[j]使其满足，i < j并且lower <= nums[j] - nums[i] <= upper。那么我们之前做过类似的题，Count of Smaller Number after Self，Reverse Pairs，我们知道这种类型的题，普遍有BST何merge sort两种解法，这里我们不讨论BST解法，感兴趣的可以参考以上的链接，我们这里主要实现merge sort的解法。和之前类似的题一样，这里我们统计reverse pair也是在merge的时候，所以我们又有了一个新的subproblem，给定两个sorted的array，a1和a2，如何在O(n)的时间里找到所有满足条件的pair, a1[i], a2[j]，其中lower <= a2[j] - a1[i] <= upper。
为了解决这个subproblem，我们先只考虑下界lower，对于例子a1 = {1,3,4}, a2 = {2,5,6}, lower = -2来说，对于a1中的每一个元素，我们找出a2中从左到右第一个满足a2[j] - a1[i] >= -2的元素，对于1来说也就是2，那么j之后所有的元素的元素都满足下界。并且j是单调递增的，也就是对于a1 i的后续元素，a2 j之前的元素都不可能让其满足条件。所以时间复杂度为O(n)。对于上界upper来说也是类似的，对于每一个i，我们找到a2中第一个使a2[j] - a1[i]  > 2的j，那么j之前的元素都是满足上界的，同理j也是一直递增的。我们将这两个结合到一起，就可以在O(n)的时间里找到同时满足上界和下界的pairs。总的时间复杂度O(n * log n)，代码入下：

	class Solution {
	public:
	int countRangeSum(vector<int>& nums, int lower, int upper) {
	int len = nums.size(), res = 0;
	if (!len)return 0;
	//caculate presum array
	vector<long long> preSum(len, 0);
	preSum[0] = nums[0];
	for (int i = 1; i < len; ++i)
	preSum[i] = static_cast<long long>(nums[i]) + preSum[i - 1];
	mergeSort(preSum, 0, len - 1, lower, upper, res);
	return res;
	}
	private:
	void mergeSort(vector<long long>& nums, int lo, int hi, int lower, int upper, int& count)
	{
	if (lo >= hi)
	{
	if (lo == hi && nums[lo] <= upper && nums[lo] >= lower)++count;
	return;
	}
	int mid = lo + (hi - lo) / 2;
	mergeSort(nums, lo, mid, lower, upper, count);
	mergeSort(nums, mid + 1, hi, lower, upper, count);
	int p1 = lo, p2 = mid + 1, p3 = mid + 1;
	//preprocess to count
	while (p1 <= mid)
	{
	//lowerbound
	while (p2 <= hi && nums[p2] - nums[p1] < lower)++p2;
	//upper bound
	while (p3 <= hi && nums[p3] - nums[p1] <= upper)++p3;
	count += p3 - p2;
	++p1;
	}
	//merge
	p1 = lo;
	p2 = mid + 1;
	int curr = 0;
	vector<long long> aux(hi - lo + 1);
	while (p1 <= mid || p2 <= hi)
	{
	if (p1 > mid) { aux[curr++] = nums[p2++]; continue; };
	if (p2 > hi) { aux[curr++] = nums[p1++]; continue; };
	if (nums[p1] <= nums[p2])aux[curr++] = nums[p1++];
	else aux[curr++] = nums[p2++];
	}
	for (int i = lo; i <= hi; ++i)
	nums[i] = aux[i - lo];
	}
	};

view raw Count of Range Sum.cpp hosted with ❤ by GitHub