327. 区间和的个数
在解题之前，先考虑如下问题：
给定两个升序排列的数组 $n_1, n_2$，试找出所有的下标对$(i,j)$，满足
\[n_2[j]−n_1[i]\in[lower,upper]\] \[\begin{align} \left\{ \begin{aligned} & n_2[l] \geq n_1[i] + lower \\ & n_2[r] \leq n_1[i] + right \\ \end{aligned} \right. \end{align}\]在已知两个数组是升序的情况下：
遍历$n_1$中的每个元素，对于每一个元素，找到$n_2$中满足$(1)$的区间，也就是找到对应的左右下标$l,r$。 例如，给定$n_1, n_2, lower=1, upper=3$
n_{1} = | 1 | 2 | 3 | 4 |
^
i
n_{2} = | 1 | 2 | 3 | 4 |
^ ^
l r
如此，我们就求出了当$i=0$时，对应的$l,r$。符合条件的下标对有$r-l+1$。
因为两个数组是升序的，所以当$i$增大时，$l,r$也只能向右移动。遍历$i$算出下标对的总和。
题目描述 ：
转化为前缀和问题
既然是区间和问题，可以想到前缀和。设前缀和数组为 $preSum$，则问题等价于求所有下标对$(i,j)$，使得
\[preSum[j] - preSum[i] \in [lower, upper]\]归并排序
对$preSum$进行归并排序。
文章开头提到的算法与本题的联系在，归并排序中，每一轮合并之前，会产生两个排序好的数组。通过这两个数组，可以算出在这一层，右侧数组内$preSum[j]$和左侧数组$preSum[i]$的差，如果差在范围内，则说明当前下标对符合条件。截止到当前层，总共符合条件的下标和对数等于之前所有符合条件的加这一层符合条件的。
例如：
nums = [-2, 5, 1]
upper = 2
lower = -2
preSum = [0, -2, 3, 2]
Dividing:
| -2 | 0 | 2 | 3 |
-> | 0 | -2 | | 3 | 2 |
-> | 0 | | -2 | | 3 | | 2 |
----------------------------------------------------------------
Conquering:
-> | 0 | | -2 | | 3 | | 2 |
Before merging:
-2 - 0 ∈ [-2,2] 2 - 3 ∈ [-2,2]
-> return++ -> return++
-> | -2 | 0 | | 2 | 3 |
Before merging:
2 - (-2) = 4 > 2 x
2 - 0 ∈ [-2,2] -> return++
3 - (-2) = 5 > 2 x
3 - 0 = 3 > 2 x
-> | -2 | 0 | 2 | 3 |
=> return = 3