昨天一个小伙伴私信问我了这道题目，乍一看这不明显的前缀和？（我还是想得太简单了！！）
327. 区间和的个数
难度困难440
给你一个整数数组 nums 以及两个整数 lower 和 upper 。求数组中，值位于范围 [lower, upper] （包含 lower 和 upper）之内的 区间和的个数 。
区间和 S(i, j) 表示在 nums 中，位置从 i 到 j 的元素之和，包含 i 和 j (i ≤ j)。
示例 1：
输入：nums = [-2,5,-1], lower = -2, upper = 2
输出：3
解释：存在三个区间：[0,0]、[2,2] 和 [0,2] ，对应的区间和分别是：-2 、-1 、2 。
示例 2：
输入：nums = [0], lower = 0, upper = 0
输出：1
提示：
1 <= nums.length <= 105
-231 <= nums[i] <= 231 - 1
-105 <= lower <= upper <= 105
题目数据保证答案是一个 32 位 的整数
最直接的思路就是作一个前缀和数组 两重for循环查询 时间复杂度O（n*2），很显然，在这个1 <= nums.length <= 105约束下，无法完成。那该怎么办？
下面的讲解基于懂得归并排序模板的基础上，不懂的自行解决;
简单了看了一下官方的一个思路（当然可以用线段树等其他高级数据结构解决本题）
归并排序
做法和求逆序对很像，都是把求解的答案来源分成三块（根据端点的位置）
【注：下面令an为presum,bn为origin】
（逆序对：若i<j,a[i]>a[j]，称之为逆序对,前缀和：a[i]-a[j] =b(j+1)+...b[i] ）
比较一下发现，两者近乎相似！都是要求一对合法的数对 （i，j）
类比逆序对的思路，我们把一个区间[l,r]分成俩,[l,mid]和[mid+1,r]
借助归并排序，先递归上述两个子区间，得到两个子区间内的合法数对的数量（i,j要么同时落在左区间要么同时落在右区间）
然后在加上一左一右的合法数对量，即我们所求答案；
你可能会疑惑：为什么或者说，怎么保证我们先 递归子区间（我们函数不是都没写完吗？怎么这么神奇？），就能得到子区间的解？
对于这个问题，我一开始也和你有同样的疑惑，但是，如果能画一个递归树，或许就很好理解了，下面展开叙述；
回到上面的定义：a[j] - a[i] = b(i+1)+...bj
那么就要求 i>=0, j>=i+1>=1,
[i如果小于0导致下标越界，j小于i+1导致区间和b(i+1)+....bj不存在]
因为这样，那么导致区间和bi+....bj只能从b1开始，b0引导的前缀和就丢失了。
所以这里插一句，在初始化presum an的时候，a[0]置空，令a[1] = b[0](我们原先都是令a[0]=b[0])，这样子就能保证遍历所有的前缀和情况了；
回到那个神奇的问题，由于我们写的是递归，要搜到最底层的时候，一定是碰到了某个基线条件：由于新的一轮的l,r是都是每次之前开始的l,r一分为二得到的，那么最终l和r一定会先相遇，也就是我们的基线条件l = r（l大于r当然是发生在l等于r后面，l = r的时候直接return掉了）。
我们不妨考虑基线条件前的一个状态，只有两个数[a,b]，由上述，我们一分为二，
递归左区间[a]，右区间[b],（递归完了这两个的时候以后再说，先递归！！）。
由上述前缀和定义可知，当l = r ，区间不存在，当然无所谓区间和，那么个数就是0，[a]和[b]这两个子区间的个数就是0。那么，我们就用最简单的手段，完成了上面提到的神奇的任务：递归得到子区间的合法数对。所以，递归完了这两个子区间，区间为[a,b]的这次递归的答案:res+= 0 + 0，然后在研究端点一左一右的合法数对量（这个是我们手动求的过程，不需要递归，后面会讲到），即可得到本次递归的结果；
那么，设想[a,b]的上一层是区间是[a,b,c,d]，也就是求解[a,b]区间的合法对数量这个过程是在递归[a,b,c,d]这层区间时被调用的，此时，而且可以非常肯定地说，我们已经求出了[a,b]这个区间的合法对数量，也就是[a,b,c,d]这个区间的一个子区间的合法对数量！！...[c,d]区间同理.然后我们再去研究一左一右的情况....这样[a,b,c,d]这个区间的合法对就知晓了；就这样，从基线条件的状态下，从每一次小规模的子区间一步步被求解并返回到上一层，最终获得我们总的规模（总的区间）下的解；说明是合理并且巧妙的。
既然，子区间递归那一步说清楚了，现在任务落在求解端点一左一右约束下的数对
这个解法从官方那学习到了，很巧妙哈哈，不过官方有些细节的地方没说情况（为啥要排序，排序合理吗会影响结果吗？）
下面叙述：
左端点i落在[l,mid]，右端点j落在[mid+1,r]
也就是在上述的约数下，求(i，j），会先想到两重循环遍历，复杂度((n/2)**2=n**2/4)，不大可行；
考虑这样一种的做法：
我们先把[l,mid]的值以Sn的形式写出来：sl,s(l+1)...smid ①
同样的,[mid+1,r] :s(mid+1)...sr②
等价于我们从①②中分别取一个出来，使得它是合法数对（就是low<=s[j]-s[r]<=up）
那么我们把它打乱顺序有关系吗？会影响我们的解集吗？显然不会。能匹配的最终就是能匹配上；
那么，我们来把他排序（大显神功）
这样做有什么用呢？细说：
我们先遍历第一个区间，每次固定第一个数：s[i]
然后由于②经过升序排序，我们找到第一个p（左指针）使得s[p]-s[i]>=low，那么，由于递增，p以后的一定都是满足减去s[i]>=low的，然后我们再来一个右指针q，
指向最后一个s[q]-s[i]<=low的后一个位置。那么下标[p,q-1]都是合法对，res+=q-p即可；
这里有几个细节的地方，也就是优化的关键点：
p（左指针）是从mid+1开始的（这个很显然，因为我们要在第二个区间里面找到一个j就要从开头开始寻找），q（右指针）也是从mid+1开始的，每次循环直到指向第一个不符合的j的位置。这里有个疑惑，从mid+1开始，这样寻找q的做法合理，但是为什么不能从r开始，不断左移，直到指向最后一个合法解，然后区间长度q-p+1累加到答案上（我开始就是这么做的），原因是这样的：
还是因为递增，试想，当i = l的时候，我们寻找右指针q，按照上面（错误）的解法，假设找到了，即满足a[q] - a[l]<=up，且q是最后一个位置。
那么，当i = l+1的时候，，由于递增的条件必定有：a[q] - a[l+1]<=a[q] - a[l]<=up，那么此时等于说右指针q就不发生移动了！(l+2,l+3..都是如此)
这样会导致什么？解的缺失（减少）
因为a[q]-a[l]<=up这个式子，up是定值，[mid+1,r]区间升序，a[l]越大，意味着a[q]需要越大，而一开始，a[0]代入上面这个式子，等于说a[q]已经移动到了最小的值，那么随着a[l]的增大，a[q]-a[l]<=up必定满足；然而，实际上，对于大于a[0]的数，a[q]其实可以指向更大的数，也就说:我们要把所有的存在的q给找出来！
如果按照错误的做法，就是恒成立做法，导致漏解，如果是正确的做法，等价于求存在性问题，把所有的解都给我找出来！
所以，需要两个指针都是从mid+1开始找；左指针找到源头，右指针负责找到广搜所有点！
所以，现在确定了遍历方向的问题，迎来最后一个优化点：
难道i,j每次循环都要从mid+1开始找吗？
答案是否定的，i,j应该继承上一轮循环的状态
证明合理性：某次循环，第一个区间指到k,第二个区间的左指针指向第一个合法对，
使得a[l]-a[k]>=lower*
，那么下一次循环，由于递增a[k+1]>=a[k]，要使得*式成立，l至少不动
某次循环，j指向第一个不合法对，使得a[j]-a[k]>up*，由于递增a[k+1]>=a[k]，
要使得上述式子成立，j至少不动。所以，每次循环左右指针继承上一轮结果即可；
最后累加到结果，就是我们最终的答案了；
然后接下来就是归并排序的模板了，排个序（双指针+扫尾）；
这里会回过头来，再复习一下，为什么先递归两个子区间（函数都没写完呢），就能保证得到两个有序的子区间（这其实就是我们刚刚上面讲的那个问题）
一样的，当碰到基线条件的，l = r（一个数不处理：等价于我们把这两个区间（很特殊的区间，只有一个数字）给排好了），回归到上一层，即两个数的区间，然后再双指针，扫尾...这样子两个数的区间这一层递归也就好了...一直回归，直到完成最大规模的解，即可；
奔赴热爱 奔赴山海 体会数学之美 算法之美 ！
