[归并排序]leetcode327：区间和的个数

题目：

题解：

思路：归并排序

1）对于区间和的快速求解需要使用前缀和，由于 a 中的元素有正有负，所以前缀和数组不是单调递增的，我们可以对前缀和数组进行归并排序，顺便计算区间和的个数，求 pre[j]-pre[i]∈[lower,upper] 的 (i,j) 的个数。2）思考如何利用两个升序数组n1,n2求出n2[j]-n1[i]∈[lower,upper]？
3）在解决这一问题后，原问题就迎刃而解了：我们采用归并排序的方式，能够得到左右两个数组排序后的形式，以及对应的下标对数量。对于原数组而言，若要找出全部的下标对数量，只需要再额外找出左端点在左侧数组，同时右端点在右侧数组的下标对数量，而这正是我们此前讨论的问题。

代码如下：

const int N = 1e5+10;using LL = long long;class Solution {public: // 思路：归并排序，在两个升序数组中寻找下标对的区间和在[lower,upper]之间。每次统计第二个区间的n2[l]>=n1[0]+lower,n2[r]>n1[0]+uperr，这样的话[l,r)范围内的区间和都在[lower,upper]之间了。由于n1是递增的，因此l，r只能向右移动才能进行统计了。 LL pre[N],b[N]; int countRangeSum(vector& a, int lower, int upper) { int n=a.size(); memset(pre,0,sizeof pre),memset(b,0,sizeof b); // 预处理前缀和数组 for(int i=1;i<=n;++i)pre[i]=pre[i-1]+a[i-1]; return merge(lower,upper,0,n); } int merge(int lower,int upper,int l,int r){ if(l>=r)return 0; // 1.确定分界点，递归处理左右两段 int mid=(l+r)>>1; int res=merge(lower,upper,l,mid)+merge(lower,upper,mid+1,r); // 2.统计下标对的数量 int i=l,_l=mid+1,_r=mid+1; while(i<=mid) { // 直到pre[_l]-pre[i]>=lower为止；直到pre[_r]-pre[i]>upper为止；这样区间[_l,_r)满足情况了 while(_l<=r&&pre[_l]-pre[i]mid)b[k++]=pre[j++]; else if(j>r)b[k++]=pre[i++]; else{ if(pre[i]