区间和的个数为什么可以用前缀和 + 归并排序统计？（LeetCode 327）

简化版

区间和 sum(i..j) 可写成前缀和差 prefix[j+1] - prefix[i]。问题变成统计有多少对 i < j 满足 lower <= prefix[j] - prefix[i] <= upper。用归并排序分治前缀和数组：递归统计左右内部，合并前用双指针在右半有序前缀中为每个左前缀找合法范围，再归并排序。

详细版

先构造 prefix[0]=0，prefix[k+1]=prefix[k]+nums[k]。任何连续子数组和都等于两个前缀和之差。于是对每个左前缀 prefix[i]，要找右侧前缀 prefix[j] 落在 [prefix[i]+lower, prefix[i]+upper] 内的数量。

分治时，左右两半前缀和分别已经排序。跨半区统计时，对左半每个值 x，在右半用两个单调指针 l 和 r 找第一个 >= x+lower 和第一个 > x+upper 的位置，贡献是 r - l。因为左半按升序扫描，两个指针只向右移动，跨半统计是 O(n)。

每层统计 O(n)、共 O(log n) 层，时间 O(n log n)，辅助空间 O(n)。前缀和要用 long，避免整数溢出。

完整版教学

一、把子数组和转成两个前缀和的差

子数组 nums[i..j] 的和可以写成 prefix[j+1] - prefix[i]。这一步把“枚举所有区间”变成“枚举所有前缀和对”。例如 nums = [-2,5,-1]，前缀和是 [0,-2,3,2]。

若 lower=-2, upper=2，合法区间有 [-2]、[-1]、[-2,5,-1]，共 3 个。对应前缀和差分别是 -2 - 0 = -2、2 - 3 = -1、2 - 0 = 2。

prefix: 0, -2, 3, 2
合法差: prefix[j] - prefix[i] in [-2, 2], i < j

二、为什么不能直接双重循环

前缀和有 n + 1 个，暴力枚举所有 (i,j) 是 O(n^2)。当 n 到 100000 时，配对数量约 5 * 10^9，不可接受。

分治的思路是：把前缀和数组切成左右两半。合法对分三类：左半内部、右半内部、跨左右两半。前两类递归处理，跨半区在“左右都有序”的条件下线性统计。

记忆钩子：区间和个数不是在原数组上归并，而是在前缀和数组上统计“右前缀 - 左前缀”的合法范围。

三、跨半区如何用双指针计数

假设左半和右半前缀和都已经排序。对左半某个值 x，我们要找右半中满足：

lower <= y - x <= upper
等价于
x + lower <= y <= x + upper

由于右半有序，可以维护两个指针：l 指向第一个 >= x + lower 的位置，r 指向第一个 > x + upper 的位置。区间 [l, r) 中的右半前缀都能和 x 形成合法区间，贡献 r - l。

当左半 x 按升序增大时，x + lower 和 x + upper 也增大，所以 l、r 都只会向右移动，不会回退。这让跨半统计从 O(n log n) 或 O(n^2) 降到 O(n)。

四、代码模板

统计完跨半区后，还要把当前区间归并成有序，否则上一层无法继续用双指针。也就是说每个递归函数同时返回“计数”并维护“区间有序”。

int countRangeSum(int[] nums, int lower, int upper) {
    long[] prefix = new long[nums.length + 1];
    for (int i = 0; i < nums.length; i++) {
        prefix[i + 1] = prefix[i] + nums[i];
    }
    return (int) sortAndCount(prefix, 0, prefix.length, lower, upper, new long[prefix.length]);
}

long sortAndCount(long[] pre, int lo, int hi, int lower, int upper, long[] tmp) {
    if (hi - lo <= 1) return 0;
    int mid = lo + (hi - lo) / 2;
    long count = sortAndCount(pre, lo, mid, lower, upper, tmp)
               + sortAndCount(pre, mid, hi, lower, upper, tmp);

    int l = mid, r = mid;
    for (int i = lo; i < mid; i++) {
        while (l < hi && pre[l] - pre[i] < lower) l++;
        while (r < hi && pre[r] - pre[i] <= upper) r++;
        count += r - l;
    }

    int i = lo, j = mid, k = lo;
    while (i < mid && j < hi) tmp[k++] = pre[i] <= pre[j] ? pre[i++] : pre[j++];
    while (i < mid) tmp[k++] = pre[i++];
    while (j < hi) tmp[k++] = pre[j++];
    for (int p = lo; p < hi; p++) pre[p] = tmp[p];
    return count;
}

这里用半开区间 [lo, hi) 可以减少边界歧义。返回值用 long 更稳，最终按题目返回 int。

五、用样例走一遍

nums=[-2,5,-1]，prefix=[0,-2,3,2]。分治排序过程中，跨半统计会发现 0 与右侧 2 的差为 2，合法；3 与右侧 2 的差为 -1，合法；0 与 -2 的差为 -2，合法。

左前缀 x	合法右前缀 y 范围	命中
0	`[-2,2]`	`-2,2`
-2	`[-4,0]`	无
3	`[1,5]`	`2`

真实递归层次里这些命中分布在不同层，但总原则一样：只统计 i < j 的前缀对，且跨半只统计一次。

六、常见误区与追问

误区：直接对原数组归并。 判断区间和需要前缀和差，归并对象应是 prefix 数组。
误区：忘记 prefix[0]=0。 会漏掉从下标 0 开始的子数组。
误区：用 int 存前缀和。 多个大数累加可能溢出，应使用 long。
追问：为什么 r 条件是 <= upper？ 因为 upper 是闭区间上界，r 要停在第一个大于 upper 的位置。
追问：为什么统计后还要归并？ 上一层依赖当前区间有序，否则双指针范围统计失效。
追问：能用树状数组吗？ 可以离散化前缀和及边界值，再边扫边查频次，复杂度也是 O(n log n)。

七、加强记忆

区间和个数记成“前缀和差落区间，归并时数跨半合法对”。对左前缀 x，右前缀必须落在 [x+lower, x+upper]；右半有序，所以用两个单调指针找窗口大小。统计只是副产品，当前区间归并有序才是让上一层继续工作的前提。

简化版

详细版