[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)，代码入下：