算法刷题系列（十五）：前缀和——把区间和变成前缀差

算法刷题系列（十五）：前缀和——把区间和变成前缀差

移除元素一章维护的是“扫描到这里，哪些元素已经保留”。本篇维护的是累计量：从数组开头加到当前位置的和。累计结果一旦计算出来，任意区间的和就可以由两个前缀相减得到。

前缀和的价值不只是加速区间查询。把“区间和等于目标值”改写成两个前缀之差后，还可以用哈希表统计符合条件的子数组。

一、半开区间定义

给定数组 a，定义长度为 n + 1 的前缀数组：

prefix[0] = 0
prefix[i + 1] = prefix[i] + a[i]

于是 prefix[i] 表示原数组前 i 个元素的和。半开区间 [left, right) 的和是：

sum(left, right) = prefix[right] - prefix[left]

使用半开区间有两个好处：长度直接是 right - left；从数组开头开始的区间可以自然表示为 [0, right)。

二、静态区间查询

例如：

a      = [4, -2, 7, 1]
prefix = [0, 4, 2, 9, 10]

查询下标区间 [1, 4)，即 [-2, 7, 1]：

prefix[4] - prefix[1] = 10 - 4 = 6

建立前缀数组耗时 O(n)，每次查询 O(1)。如果只查询一次，直接求和可能更简单；当查询很多次时，预处理更有价值。静态前缀和不适合频繁修改原数组，因为一次修改会影响后续多个前缀值。

三、把目标区间转为前缀差

考虑连续子数组 [left, right) 的和为 target：

prefix[right] - prefix[left] = target

移项后得到：

prefix[left] = prefix[right] - target

从左向右扫描时，当前前缀为 current，只要知道之前出现过多少次 current - target，就能知道以当前位置结尾的目标子数组数量。

哈希表存储“某个前缀和出现的次数”。初始化时要放入 {0: 1}，表示空前缀出现一次；这样从数组下标 0 开始的答案也能被计入。

四、原创例子：统计总和为 3 的子数组

nums = [2, -1, 2], target = 3

扫描前缀和：

读入值	当前前缀	需要的旧前缀 current - target	新增子数组数
2	2	-1	0
-1	1	-2	0
2	3	0	1

末尾前缀为 3，之前的空前缀 0 出现过一次，因此整个数组是一个答案。

五、Java 实现

import java.util.HashMap;
import java.util.Map;

public class PrefixSums {
    public static long[] buildPrefix(int[] values) {
        if (values == null) {
            throw new IllegalArgumentException("values must not be null");
        }
        long[] prefix = new long[values.length + 1];
        for (int i = 0; i < values.length; i++) {
            prefix[i + 1] = prefix[i] + values[i];
        }
        return prefix;
    }

    public static long rangeSum(long[] prefix, int left, int right) {
        if (prefix == null) {
            throw new IllegalArgumentException("prefix must not be null");
        }
        if (left < 0 || left > right || right >= prefix.length) {
            throw new IndexOutOfBoundsException("invalid half-open range");
        }
        return prefix[right] - prefix[left];
    }

    public static long countSubarraysWithSum(int[] values, long target) {
        if (values == null) {
            throw new IllegalArgumentException("values must not be null");
        }

        Map<Long, Long> frequency = new HashMap<>();
        frequency.put(0L, 1L);
        long prefix = 0;
        long answer = 0;

        for (int value : values) {
            prefix += value;
            answer += frequency.getOrDefault(prefix - target, 0L);
            frequency.put(prefix, frequency.getOrDefault(prefix, 0L) + 1);
        }
        return answer;
    }
}

先查询，再把当前前缀加入频次表，确保匹配的是严格位于当前位置之前的前缀。

六、Python 实现

def build_prefix(values: list[int]) -> list[int]:
    if values is None:
        raise ValueError("values must not be None")
    prefix = [0] * (len(values) + 1)
    for index, value in enumerate(values):
        prefix[index + 1] = prefix[index] + value
    return prefix

def query_range(prefix: list[int], left: int, right: int) -> int:
    if prefix is None:
        raise ValueError("prefix must not be None")
    if left < 0 or left > right or right >= len(prefix):
        raise IndexError("invalid half-open range")
    return prefix[right] - prefix[left]

def count_subarrays_with_sum(values: list[int], target: int) -> int:
    if values is None:
        raise ValueError("values must not be None")

    frequency = {0: 1}
    prefix = 0
    answer = 0
    for value in values:
        prefix += value
        answer += frequency.get(prefix - target, 0)
        frequency[prefix] = frequency.get(prefix, 0) + 1
    return answer

prefix = build_prefix([4, -2, 7, 1])
assert query_range(prefix, 1, 4) == 6
assert count_subarrays_with_sum([2, -1, 2], 3) == 1
assert count_subarrays_with_sum([0, 0, 0], 0) == 6

七、复杂度与边界

• 静态区间查询：预处理 O(n) 时间、O(n) 空间，每次查询 O(1)。
• 目标子数组计数：期望 O(n) 时间，哈希表空间最坏 O(n)。
• 使用 long 保存 Java 累计和与答案，避免数组元素较大时 int 溢出。
• 数组中允许负数。与滑动窗口不同，前缀和加哈希表不依赖元素非负。

如果数组会频繁单点更新并且需要区间查询，静态前缀数组就不是理想结构；后续可以学习树状数组或线段树。

八、常见错误

1. 前缀数组长度只开 n：半开定义需要 n + 1 个位置。
2. 混用闭区间和半开区间：先固定接口语义，避免 right + 1 到处出现。
3. 漏掉初始频次 {0: 1}：会漏计从开头开始的目标子数组。
4. 先插入当前前缀再查询：在某些目标下可能把空区间计入。
5. 只记录前缀是否出现：要统计子数组数量，必须记录出现频次。
6. 以为前缀和能免费支持修改：数组变化后，相关前缀值也要更新。

小结

前缀和把区间和变为两个累计量之差。静态区间查询直接使用 prefix[right] - prefix[left]；目标子数组计数则把前缀频次放进哈希表。半开区间和空前缀初始化可以显著减少边界分支。