概述：为什么前缀和是区间问题的第一反应

学完滑动窗口之后，很多读者会发现一类题反复出现：

• 多次询问某个区间的和
• 统计某种满足条件的连续子数组
• 在二维矩阵里快速求某个子矩形的元素和

这类题如果每次都老老实实从头加到尾，代码不复杂，但效率通常很差。
而前缀和的价值就在于：

它可以把“重复计算一段区间”的过程，变成“先预处理一次，之后快速查询”。

前缀和是算法题里非常基础、但又非常高频的一种技巧。
它本身并不复杂，但真正值得掌握的是两件事：

1. 什么时候一眼就该想到前缀和
2. 前缀和如何和哈希表、二维数组等模型组合使用

学完这篇，你应该能把“区间和问题”迅速转化为前缀和模型，并掌握一维、二维以及“前缀和 + 哈希表”的常见套路。

核心概念：前缀和到底是什么

前缀和，顾名思义，就是“从开头累加到当前位置的和”。

对于数组 nums：

nums = [2, 1, 3, 4, 5]

如果我们定义：

prefix[i] = nums[0] 到 nums[i - 1] 的元素和

那么通常会写成：

prefix[0] = 0
prefix[1] = 2
prefix[2] = 2 + 1 = 3
prefix[3] = 2 + 1 + 3 = 6
prefix[4] = 2 + 1 + 3 + 4 = 10
prefix[5] = 2 + 1 + 3 + 4 + 5 = 15

也就是说，prefix 数组往往会比原数组多开一个位置，方便统一处理边界。

前缀和最核心的公式

如果你想求区间：

[left, right]

的元素和，那么有：

$$sum(left,right)=prefix[right+1]-prefix[left]$$

这个公式就是前缀和的全部核心。

因为：

• prefix[right + 1] 表示从开头加到 right
• prefix[left] 表示从开头加到 left - 1
• 两者一减，刚好剩下 left 到 right

前缀和不是直接去算某一段，而是先保存“从头到这里”的累计结果，查询时再做一次减法。

原理：为什么前缀和能把区间求和优化到 O(1)

先看最直接的做法。

如果题目要多次询问区间和，例如：

• 求 [0, 3] 的和
• 求 [2, 5] 的和
• 求 [1, 7] 的和

暴力思路通常是：

1. 每次拿到 left 和 right
2. 再从 left 循环加到 right

如果查询很多次，总复杂度会很高。

而前缀和的思路是：

1. 先花 O(n) 预处理出 prefix
2. 后续每次查询只做一次减法

整个过程可以理解成：

这意味着：

• 预处理复杂度：O(n)
• 单次查询复杂度：O(1)

如果一共有很多次查询，这种优化非常划算。

先建立框架：什么题一眼该想到前缀和

初学阶段，你可以先记住下面几个信号。

1. 题目反复询问区间和

只要出现：

• 多次区间求和
• 多次区间计数
• 多次连续子数组统计

前缀和通常都值得优先考虑。

2. 题目和“连续子数组”有关

比如：

• 和为 k 的子数组有多少个
• 是否存在某段连续区间满足某种和条件
• 最长或最短满足条件的连续子数组

这类题很多都能把“区间和”转写成“两个前缀和之差”。

3. 题目需要大量重复计算

如果你发现自己在双层循环里不断做：

sum += nums[j];

那就应该警惕：这个地方是否能预处理成前缀和。

只要题目涉及“连续区间 + 重复统计”，前缀和通常就是第一反应。

模板一：一维前缀和的标准写法

先把最基础的模板写熟。

public static int[] buildPrefixSum(int[] nums) {
    int n = nums.length;
    int[] prefix = new int[n + 1];

    for (int i = 0; i < n; i++) {
        prefix[i + 1] = prefix[i] + nums[i];
    }

    return prefix;
}

public static int rangeSum(int[] prefix, int left, int right) {
    return prefix[right + 1] - prefix[left];
}

这里最值得注意的是：

• prefix[0] = 0
• prefix[i + 1] = prefix[i] + nums[i]

这样写的好处是边界非常统一，不需要单独讨论 left = 0 的情况。

为什么推荐“多开一位”

很多初学者喜欢定义：

prefix[i] = nums[0] 到 nums[i] 的和

这种写法也能做，但在求区间和时容易多写边界判断。
而“多开一位”的版本几乎是算法题里最常用、最稳妥的形式。

一维前缀和最标准的写法，就是构造长度 n + 1 的数组，用 prefix[right + 1] - prefix[left] 查询答案。

经典例题一：区域和检索

这类题可以看作前缀和的入门模板题。

题目大意：

给定一个整数数组，反复查询某个区间 [left, right] 的元素和。

暴力做法为什么不理想

如果每一次查询都重新遍历区间，那么：

• 单次查询是 O(right - left + 1)
• 查询次数一多，总复杂度会明显变差

前缀和的做法就是：

1. 初始化时预处理 prefix
2. 查询时直接套公式

class NumArray {
    private final int[] prefix;

    public NumArray(int[] nums) {
        prefix = new int[nums.length + 1];
        for (int i = 0; i < nums.length; i++) {
            prefix[i + 1] = prefix[i] + nums[i];
        }
    }

    public int sumRange(int left, int right) {
        return prefix[right + 1] - prefix[left];
    }
}

为什么这段代码高效

假设：

nums = [2, 1, 3, 4, 5]
prefix = [0, 2, 3, 6, 10, 15]

要求：

[1, 3]

的区间和，也就是：

1 + 3 + 4 = 8

直接计算：

prefix[4] - prefix[1] = 10 - 2 = 8

整个查询没有重新遍历数组。

时间复杂度：

构造：O(n)
查询：O(1)

空间复杂度：

O(n)

经典例题二：和为 k 的子数组

这是前缀和真正开始“进阶”的地方。

题目大意：

给定一个整数数组 nums 和一个整数 k，求和为 k 的连续子数组个数。

这道题如果只会暴力枚举，通常会想到：

1. 枚举每个起点
2. 枚举每个终点
3. 统计区间和是否等于 k

这会得到 O(n^2) 的复杂度。

先把问题转成前缀和公式

如果某个区间：

[j, i]

的和等于 k，那么有：

$$prefix[i+1]-prefix[j]=k$$

移项之后就是：

$$prefix[j]=prefix[i+1]-k$$

这句话非常关键，它告诉我们：

当我们枚举到当前位置时，只要知道之前有多少个前缀和等于 当前前缀和 - k，就知道有多少个合法子数组。

为什么要结合哈希表

因为我们需要快速知道：

• 某个前缀和值出现过几次

这正是哈希表最擅长的事情。

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

public static int subarraySum(int[] nums, int k) {
    Map<Integer, Integer> countMap = new HashMap<>();
    countMap.put(0, 1);

    int prefixSum = 0;
    int ans = 0;

    for (int num : nums) {
        prefixSum += num;

        ans += countMap.getOrDefault(prefixSum - k, 0);
        countMap.put(prefixSum, countMap.getOrDefault(prefixSum, 0) + 1);
    }

    return ans;
}

这段代码到底在做什么

可以把流程理解成下面这样：

1. 从左到右扫描数组
2. 维护当前位置的前缀和 prefixSum
3. 查找之前是否出现过 prefixSum - k
4. 如果出现过，说明存在若干段连续子数组和为 k
5. 最后再把当前前缀和记入哈希表

流程图如下：

为什么 countMap.put(0, 1) 必不可少

这是很多人第一次写这题时最容易漏掉的一行。

它表示：

• 在还没开始遍历数组之前
• 已经有一个前缀和为 0

这样当某一段“从下标 0 开始”的子数组和恰好等于 k 时，也能被正确统计到。

例如：

nums = [3]
k = 3

遍历到第一个元素后：

prefixSum = 3
prefixSum - k = 0

如果你没有提前记录 0 -> 1，这段子数组就统计不到。

前缀和 + 哈希表 的本质，是把“枚举所有区间”变成“统计之前出现过多少个目标前缀和”。

时间复杂度：

O(n)

空间复杂度：

O(n)

模板二：二维前缀和的基本思路

一维前缀和解决的是数组区间问题，二维前缀和解决的则是矩阵子区域问题。

比如题目会问：

• 某个子矩形内所有元素的和是多少
• 多次查询矩阵中的区域和

二维前缀和怎么定义

通常定义：

prefix[i][j]

表示原矩阵左上角到位置 (i - 1, j - 1) 的矩形元素和。

标准转移公式是：

$$prefix[i][j]=prefix[i-1][j]+prefix[i][j-1]-prefix[i-1][j-1]+matrix[i-1][j-1]$$

这里减去 prefix[i - 1][j - 1]，是为了避免左上重叠区域被重复计算。

二维查询公式

如果要查询子矩形：

(row1, col1) 到 (row2, col2)

则有：

$$sum=prefix[row2+1][col2+1]-prefix[row1][col2+1]-prefix[row2+1][col1]+prefix[row1][col1]$$

二维前缀和模板

public static int[][] build2DPrefixSum(int[][] matrix) {
    int m = matrix.length;
    int n = matrix[0].length;
    int[][] prefix = new int[m + 1][n + 1];

    for (int i = 1; i <= m; i++) {
        for (int j = 1; j <= n; j++) {
            prefix[i][j] = prefix[i - 1][j]
                + prefix[i][j - 1]
                - prefix[i - 1][j - 1]
                + matrix[i - 1][j - 1];
        }
    }

    return prefix;
}

public static int query2D(int[][] prefix, int row1, int col1, int row2, int col2) {
    return prefix[row2 + 1][col2 + 1]
        - prefix[row1][col2 + 1]
        - prefix[row2 + 1][col1]
        + prefix[row1][col1];
}

本质和一维完全一样，都是“先累计，再做差”，只是从线段扩展到了矩形。

前缀和到底在解决什么问题

很多人学完公式之后，还是容易把前缀和和别的技巧混在一起。
真正要抓住的是：前缀和本质上是在解决“重复统计”的问题。

常见应用可以分成下面几类：

题型	前缀和维护的内容	常见搭配
区间和查询	从开头到当前位置的累计和	单独使用
连续子数组和为 k	前缀和出现次数	哈希表
矩阵区域和查询	左上角到当前位置的累计和	二维数组
奇偶、模值统计类问题	前缀状态	哈希表 / 计数数组

所以做题时可以先问自己：

1. 题目是不是和连续区间有关？
2. 我是不是在重复求某一段的和？
3. 这段区间能不能写成两个前缀量的差？
4. 如果能写成差，还需不需要哈希表来统计次数？

前缀和真正有用的地方，不是“会写数组”，而是“会把区间问题转写成两个前缀量的关系”。

易错点：新手写前缀和最容易踩的坑

1. prefix 数组下标定义混乱

最常见的问题不是公式不会，而是自己把：

• prefix[i] 到底表示什么
• 包不包含 nums[i]

写乱了。

建议统一采用：

prefix[i] 表示前 i 个元素之和

这样最稳。

2. 忘记多开一个位置

如果不多开一位，就经常需要额外处理：

left = 0

的情况，代码更容易出错。

3. 区间公式写成了 prefix[right] - prefix[left]

如果你采用的是标准写法，那么正确公式一定是：

prefix[right + 1] - prefix[left]

这是一类高频笔误。

4. 在“前缀和 + 哈希表”题里漏掉初始化

像“和为 k 的子数组”这种题，往往必须先写：

countMap.put(0, 1);

否则从下标 0 开始的合法区间会漏算。

5. 先更新哈希表，再统计答案

在很多题里，顺序必须是：

1. 先根据当前前缀和查答案
2. 再把当前前缀和放进哈希表

如果顺序反了，就可能把当前前缀和错误地用于匹配自己。

6. 只会处理正数，忽略负数场景

有些人会把“连续子数组和”问题习惯性往滑动窗口上套。
但一旦数组中有负数，滑动窗口通常就不成立了，这时前缀和往往更稳。

7. 二维前缀和忘记减去重叠区域

二维公式里：

- prefix[i - 1][j - 1]

这一项是为了解决重复计算。
漏掉它，结果一定偏大。

复杂度总结：前缀和为什么适合“多次查询”

前缀和最大的价值，不是让第一次查询更快，而是让：

大量重复查询变得极其快速。

下面这张表很适合建立直觉：

场景	暴力做法	前缀和做法
一维区间和多次查询	每次 O(length)	预处理 O(n)，查询 O(1)
和为 k 的子数组个数	O(n^2)	O(n)
二维区域和多次查询	每次重新遍历子矩形	预处理后单次 O(1)

所以如果题目是“静态数组 + 多次查询”，前缀和通常非常合适。
但如果数组内容经常被修改，那么就要考虑线段树、树状数组等更适合动态维护的数据结构了。

前缀和特别适合“先预处理，后高频查询”的静态问题。

总结

前缀和的本质，是把区间问题转成两个累计量之差。
前缀和并不是在直接计算某一段，而是在提前保存“从头累计到这里”的信息，从而把很多区间问题压缩成常数级查询或线性级统计。

当你真正掌握这一点后，很多看起来麻烦的连续区间题，都会迅速变得清晰。