【前缀和】一文吃透前缀和算法，解锁高效数据处理的实用秘籍-CSDN博客 (2025)

前言

什么是前缀和算法呢？

前缀和算法，从本质上来说，是一种通过预处理数据来降低后续计算复杂度的算法思想。它的核心非常简单直观，就是预先计算出数组中从起始位置到每个位置的元素累加和。这样，当我们需要计算任意区间的元素和时，只需要通过简单的减法运算，就能快速得到结果，而无需再次遍历整个区间的元素。

下面，本文将通过例题介绍前缀和算法，揭示前缀和算法原理与本质！

例题

一、【模板】一维前缀和

1. 题目链接：【模板】前缀和
2. 题目描述：

描述
给定一个长度为n的数组a1，a2,….an.接下来有q次查询,每次查询有两个参数r.对于每个询问,请输出a! + al+1 + …+ ar
输入描述:
第一行包含两个整数n和q.
第二行包含n个整数,表示a1,a2,…….an·
接下来q行,每行包含两个整数l和r
1<=n,q<=10⁵
-10⁹<=a[i]<=10⁹
1≤l≤r≤n
输出描述:
输出q行,每行代表一次查询的结果
示例1
输入:3 2
1 2 4
1 2
2 3
输出：
3
6

3. 解法（前缀和）：
   算法思路：
   a. 先预处理出来⼀个「前缀和」数组： 用 dp[i] 表示： [1, i] 区间内所有元素的和，那么 dp[i - 1] 里面存的就是 [1, i - 1] 区间内所有元素的和，那么：可得递推公式： dp[i] = dp[i - 1] + arr[i] ；
   b. 使用前缀和数组，「快速」求出「某⼀个区间内」所有元素的和： 当询问的区间是 [l, r] 时：区间内所有元素的和为：dp[r] - dp[l - 1] 。

4. 代码示例：

 public static void main(String[] args) { Scanner in = new Scanner(System.in); int n = in.nextInt(), q = in.nextInt(); int[] nums = new int[n + 1]; long[] dp = new long[n + 1]; for (int i = 1; i < nums.length; i++) { nums[i] = in.nextInt(); } for (int i = 1; i < dp.length; i++) { dp[i] = dp[i - 1] + nums[i]; } while (q > 0) { int l = in.nextInt(), r = in.nextInt(); System.out.println(dp[r] - dp[l - 1]); q--; } }

二、【模板】二维前缀和

1. 题目链接：【模板】二维前缀和
2. 题目描述

描述：给你一个 n 行 m 列的矩阵 A ，下标从1开始。给你一个 n 行 m 列的矩阵 A ，下标从1开始。
接下来有 q 次查询，每次查询输入 4 个参数 x1 , y1 , x2 , y2
输入描述：
第一行包含三个整数n,m,q.
接下来n行，每行m个整数，代表矩阵的元素
接下来q行，每行4个整数x1, y1, x2, y2，分别代表这次查询的参数
1≤n,m≤1000
1≤q≤10⁵
-10⁹<=a[i][j]<=10⁹
1≤x₁<= x₂<=n
1<=y₁<=y₂ <=m
输出描述：
输出q行，每行表示查询结果。
示例1
输入：
3 4 3
1 2 3 4
3 2 1 0
1 5 7 8
1 1 2 2
1 1 3 3
1 2 3 4
复制
输出：
8
25
32

3. 解法：
   算法思路： 类比于⼀维数组的形式，如果我们能处理出来从 [0, 0] 位置到 [i, j] 位置这⽚区域内所有 元素的累加和，就可以在 O(1) 的时间内，搞定矩阵内任意区域内所有元素的累加和。因此我们 接下来仅需完成两步即可：
   ◦ 第⼀步：搞出来前缀和矩阵 这⾥就要⽤到⼀维数组里面的拓展知识，我们要在矩阵的最上⾯和最左边添加上一行和⼀列 0，这样我们就可以省去非常多的边界条件的处理（如果自行尝试直接搞出来前缀和矩阵，边界条件的处理会让你崩溃的）。处理后的矩阵就像这样
   
   这样，我们填写前缀和矩阵数组的时候，下标直接从 1 开始，能⼤胆使⽤ i - 1 , j - 1 位 置的值。 注意 dp 表与原数组 matrix 内的元素的映射关系：
   i. 从 dp 表到 matrix 矩阵，横纵坐标减⼀；
   ii. 从 matrix 矩阵到 dp 表，横纵坐标加⼀。

前缀和矩阵中 sum[i][j] 的含义，以及如何递推⼆维前缀和⽅程
a. sum[i][j] 的含义：
sum[i][j] 表示，从 [0, 0] 位置到 [i, j] 位置这段区域内，所有元素的累加和。对应下图的红色区域：

a. 递推方程： 其实这个递推方程非常像我们小学做过求图形面积的题，我们可以将 [0, 0] 位置到 [i, j]位置这段区域分解成下面的部分：

sum[i][j] = 红 + 蓝 + 绿 + ⻩，分析⼀下这四块区域：
i. ⻩⾊部分最简单，它就是数组中的 matrix[i - 1][j - 1] （注意坐标的映射关系）
ii. 单独的蓝不好求，因为它不是我们定义的状态表⽰中的区域，同理，单独的绿也是；
iii. 但是如果是红 + 蓝，正好是我们 dp 数组中 sum[i - 1][j] 的值，美滋滋；
iv. 同理，如果是红 + 绿，正好是我们 dp 数组中 sum[i][j - 1] 的值；
v. 如果把上⾯求的三个值加起来，那就是⻩ + 红 + 蓝 + 红 + 绿，发现多算了⼀部分红的⾯积， 因此再单独减去红的⾯积即可；
vi. 红的⾯积正好也是符合 dp 数组的定义的，即 sum[i - 1][j - 1]
综上所述，我们的递推⽅程就是：
sum[i][j]=sum[i - 1][j] + sum[i][j - 1] - sum[i - 1][j - 1]+matrix[i - 1][j - 1]

◦ 第⼆步：使用前缀和矩阵
题⽬的接口中提供的参数是原始矩阵的下标，为了避免下标映射错误，这⾥直接先把下标映射成
dp 表里面对应的下标： row1++, col1++, row2++, col2++
接下来分析如何使用这个前缀和矩阵，如下图（注意这里的 row 和 col 都处理过了，对应的正是 sum 矩阵中的下标）：

对于左上角 (row1, col1) 、右下⻆ (row2, col2) 围成的区域，正好是红色的部分。因此我们要求的就是红色部分的面积，继续分析几个区域：
i. 黄色，能直接求出来，就是 sum[row1 - 1, col1 - 1] （为什么减⼀？因为要剔除掉 row 这⼀行和 col 这⼀列）
ii. 绿色，直接求不好求，但是和黄色拼起来，正好是 sum 表内 sum[row1 - 1][col2]的数据；
iii. 同理，蓝色不好求，但是 蓝 + 黄 = sum[row2][col1 - 1] ；
iv. 再看看整个面积，好求嘛？非常好求，正好是 sum[row2][col2] ；
v. 那么，红色就 = 整个面积 - 黄 - 绿 - 蓝，但是绿蓝不好求，我们可以这样减：整个⾯积 -（绿 + 黄 ）-（蓝 + 黄），这样相当于多减去了⼀个黄，再加上即可综上所述：红 = 整个面积 - （绿 + 黄）- （蓝 + 黄）+ 黄，从而可得红色区域内的元素总和为：sum[row2][col2]-sum[row2][col1 - 1]-sum[row1 - 1][col2]+sum[row1 - 1][col1 - 1]

4. 代码示例：

 public static void main1(String[] args) { Scanner in = new Scanner(System.in); int n = in.nextInt(), m = in.nextInt(), q = in.nextInt(); int[][] array = new int[n + 1][m + 1]; long[][] dp = new long[n + 1][m + 1]; for (int i = 1; i <= n; i++) { for (int j = 1; j <= m; j++) { array[i][j] = in.nextInt(); } } for (int i = 1; i <= n; i++) { for (int j = 1; j <= m; j++) { dp[i][j] = dp[i - 1][j] + dp[i][j - 1] - dp[i - 1][j - 1] + array[i][j]; } } while (q > 0) { int x1 = in.nextInt(), y1 = in.nextInt(), x2 = in.nextInt(), y2 = in.nextInt(); System.out.println(dp[x2][y2] - dp[x1 - 1][y2] - dp[x2][y1 - 1] + dp[x1 - 1][y1 - 1]); q--; } }

三、寻找数组的中心下标

1. 题目链接：寻找数组的中心下标
2. 题目描述：

给你⼀个整数数组 nums ，请计算数组的 中⼼下标 。 数组 中⼼下标 是数组的⼀个下标，其左侧所有元素相加的和等于右侧所有元素相加的和。
如果中心下标位于数组最左端，那么左侧数之和视为 0 ，因为在下标的左侧不存在元素。这⼀点对
于中心下标位于数组最右端同样适⽤。 如果数组有多个中⼼下标，应该返回 最靠近左边的那⼀个。如果数组不存在中⼼下标，返回 -1 。
示例 1： 输⼊：nums = [1, 7, 3, 6, 5, 6]
输出：3
解释： 中⼼下标是 3 。 左侧数之和 sum = nums[0] + nums[1] + nums[2] = 1 + 7 + 3 = 11 ， 右侧数之和 sum = nums[4] + nums[5] = 5 + 6 = 11 ，⼆者相等。
⽰例 2： 输⼊：nums = [1, 2, 3]
输出：-1
解释： 数组中不存在满⾜此条件的中⼼下标。
⽰例 3： 输⼊：nums = [2, 1, -1]
输出：0
解释： 中心下标是 0 。 左侧数之和 sum = 0 ，（下标 0 左侧不存在元素），右侧数之和 sum = nums[1] + nums[2] = 1 + -1 = 0 。
提示： 1 <= nums.length <= 10^4
-1000 <= nums[i] <= 1000

3. 解法（前缀和）：
   算法思路：
   从中心下标的定义可知，除中⼼下标的元素外，该元素左边的「前缀和」等于该元素右边的「后缀和」。
   ▪ 因此，我们可以先预处理出来两个数组，⼀个表示前缀和，另⼀个表示后缀和。
   ▪ 然后，我们可以用⼀个 for 循环枚举可能的中心下标，判断每⼀个位置的「前缀和」以及 「后缀和」，如果二者相等，就返回当前下标。
4. 代码示例：

public int pivotIndex(int[] nums) { // lsum[i] 表⽰：[0, i - 1] 区间所有元素的和 // rsum[i] 表⽰：[i + 1, n - 1] 区间所有元素的和 int n = nums.length; int[] lsum = new int[n]; int[] rsum = new int[n]; // 预处理前缀和后缀和数组 for (int i = 1; i < n; i++) lsum[i] = lsum[i - 1] + nums[i - 1]; for (int i = n - 2; i >= 0; i--) rsum[i] = rsum[i + 1] + nums[i + 1]; // 判断 for (int i = 0; i < n; i++) if (lsum[i] == rsum[i]) return i; return -1; }

四、除自身以外数组的乘积

1. 题目链接：除自身以外数组的乘积
2. 题目描述：

给你⼀个整数数组 nums，返回数组 answer ，其中 answer[i] 等于 nums 中除 nums[i] 之外其余各元素的乘积 。 题目数据 保证数组 nums 之中任意元素的全部前缀元素和后缀的乘积都在 32 位 整数范围内。请不要使用除法，且在 O(n) 时间复杂度内完成此题。
示例 1:
输⼊: nums = [1,2,3,4]
输出: [24,12,8,6]
示例 2:
输⼊: nums = [-1,1,0,-3,3]
输出: [0,0,9,0,0]
提示： 2 <= nums.length <= 105
-30 <= nums[i] <= 30
保证数组 nums 之中任意元素的全部前缀元素和后缀的乘积都在 32 位整数范围内

3. 解法（前缀和数组）：
   算法思路：
   注意题目的要求，不能使用除法，并且要在 O(N) 的时间复杂度内完成该题。那么我们就不能使用暴力的解法，以及求出整个数组的乘积，然后除以单个元素的方法。
   继续分析，根据题意，对于每⼀个位置的最终结果 ret[i] ，它是由两部分组成的：
   i. nums[0] * nums[1] * nums[2] * … * nums[i - 1]
   ii. nums[i + 1] * nums[i + 2] * … * nums[n - 1]
   于是，我们可以利用前缀和的思想，使用两个数组 post 和 suf，分别处理出来两个信息：
   i. post 表示：i 位置之前的所有元素，即 [0, i - 1] 区间内所有元素的前缀乘积，
   ii. suf 表示： i 位置之后的所有元素，即 [i + 1, n - 1] 区间内所有元素的后缀乘积 然后再处理最终结果。
4. 代码示例：

public int[] productExceptSelf(int[] nums) { // lprod 表⽰：[0, i - 1] 区间内所有元素的乘积 // rprod 表⽰：[i + 1, n - 1] 区间内所有元素的乘积 int n = nums.length; int[] lprod = new int[n]; int[] rprod = new int[n]; lprod[0] = 1; rprod[n - 1] = 1; for (int i = 1; i < n; i++) { // 预处理前缀积以及后缀积 1 for(int i = 1; i < n; i++) lprod[i] = lprod[i - 1] * nums[i - 1]; } for (int i = n - 2; i >= 0; i--) rprod[i] = rprod[i + 1] * nums[i + 1]; // 处理结果数组 int[] ret = new int[n]; for (int i = 0; i < n; i++) ret[i] = lprod[i] * rprod[i]; return ret; }

五、和为 k 的子数组

1. 题目链接：和为 k 的子数组

2. 题目描述：

   给你⼀个整数数组 nums 和⼀个整数 k ，请你统计并返回该数组中和为 k 的连续⼦数组的个数 。
   ⽰例 1：
   输⼊：nums = [1,1,1], k = 2
   输出：2
   ⽰例 2：
   输⼊：nums = [1,2,3], k = 3
   输出：2
   提⽰：
   1 <= nums.length <= 2 * 10^4
   -1000 <= nums[i] <= 1000
   -10^7 <= k <= 10^7

3. 解法⼀（将前缀和存在哈希表中）：
   算法思路：
   设 i 为数组中的任意位置，⽤ sum[i] 表⽰ [0, i] 区间内所有元素的和。 想知道有多少个「以 i 为结尾的和为 k 的子数组」，就要找到有多少个起始位置为 x1, x2, x3… 使得 [x, i] 区间内的所有元素的和为 k 。那么 [0, x] 区间内的和是不是就是
   sum[i] - k 了。于是问题就变成：
   ◦ 找到在 [0, i - 1] 区间内，有多少前缀和等于 sum[i] - k 的即可。 我们不⽤真的初始化⼀个前缀和数组，因为我们只关心在 i 位置之前，有多少个前缀和等于sum[i] - k 。因此，我们仅需用一个哈希表，⼀边求当前位置的前缀和，一边存下之前每⼀种前缀和出现的次数。

4. 代码示例：

 public int subarraySum(int[] nums, int k) { Map<Integer, Integer> hash = new HashMap<Integer, Integer>(); hash.put(0, 1); int sum = 0, ret = 0; for (int x : nums) { sum += x; // 计算当前位置的前缀和 ret += hash.getOrDefault(sum - k, 0); // 统计结果 hash.put(sum, hash.getOrDefault(sum, 0) + 1); // 把当前的前缀和丢到哈希表⾥⾯ } return ret; }

六、和可被 K 整除的子数组

1. 题目链接：和可被 K 整除的子数组
2. 题目描述：

给定⼀个整数数组 nums 和⼀个整数 k ，返回其中元素之和可被 k 整除的（连续、非空） 子数组的数目。 子数组是数组的 连续部分。
示例 1：
输⼊：
nums = [4,5,0,-2,-3,1], k = 5
输出：7
解释：有 7 个子数组满足其元素之和可被 k = 5 整除：
[4, 5, 0, -2, -3, 1], [5], [5, 0], [5, 0, -2, -3], [0], [0, -2, -3], [-2, -3]
示例 2:
输⼊:
nums = [5], k = 9
输出: 0
提示: 1 <= nums.length <= 3 * 104
-10⁴ <= nums[i] <= 10⁴
2 <= k <= 10⁴

3. 解法（前缀和在哈希表中）：
   本题需要的前置知识：
   • 同余定理 如果 (a - b) % n == 0 ，那么我们可以得到⼀个结论： a % n == b % n 。用文字叙述就是，如果两个数相减的差能被 n 整除，那么这两个数对 n 取模的结果相同。
   例如： (26 - 2) % 12 == 0 ，那么 26 % 12 == 2 % 12 == 2 。
   设 i 为数组中的任意位置，用 sum[i] 表⽰ [0, i] 区间内所有元素的和。
   • 想知道有多少个「以 i 为结尾的可被 k 整除的子数组」，就要找到有多少个起始位置为 x1, x2, x3… 使得 [x, i] 区间内的所有元素的和可被 k 整除。
   • 设 [0, x - 1] 区间内所有元素之和等于 a ， [0, i] 区间内所有元素的和等于 b ，可得(b - a) % k == 0 。
   • 由同余定理可得， [0, x - 1] 区间与 [0, i] 区间内的前缀和同余。于是问题就变成：
   ◦ 找到在 [0, i - 1] 区间内，有多少前缀和的余数等于 sum[i] % k 的即可。
   我们不用真的初始化⼀个前缀和数组，因为我们只关心在 i 位置之前，有多少个前缀和等于sum[i] - k 。因此，我们仅需用一个哈希表，一边求当前位置的前缀和，⼀边存下之前每⼀种前缀和出现的次数。
4. 代码示例：

 public int subarraysDivByK(int[] nums, int k) { Map<Integer, Integer> hash = new HashMap<Integer, Integer>(); hash.put(0 % k, 1); int sum = 0, ret = 0; for (int x : nums) { sum += x; // 计算当前位置的前缀和 int r = (sum % k + k) % k; ret += hash.getOrDefault(r, 0); // 统计结果 hash.put(r, hash.getOrDefault(r, 0) + 1); } return ret; }

七、连续数组

1.题目链接：连续数组
2. 题目描述：

给定⼀个⼆进制数组 nums , 找到含有相同数量的 0 和 1 的最长连续子数组，并返回该⼦数组的⻓度。
示例 1:
输入: nums = [0,1]
输出: 2
说明:[0, 1] 是具有相同数量 0 和 1 的最长连续⼦数组。
示例 2:
输入: nums = [0,1,0]
输出: 2
说明:
[0, 1] (或 [1, 0]) 是具有相同数量 0 和 1 的最⻓连续⼦数组。
提示：1 <= nums.length <= 10⁵
nums[i] 不是 0 就是 1

3. 解法（前缀和在哈希表中）：
   算法思路：
   稍微转化⼀下题目，就会变成我们熟悉的题：
   • 本题让我们找出⼀段连续的区间， 0 和 1 出现的次数相同。
   • 如果将 0 记为 -1 ， 1 记为 1 ，问题就变成了找出一段区间，这段区间的和等于 0 。
   • 于是，就和 和为 K 的子数组 这道题的思路⼀样
   设 i 为数组中的任意位置，⽤ sum[i] 表⽰ [0, i] 区间内所有元素的和。 想知道最大的「以 i 为结尾的和为 0 的⼦数组」，就要找到从左往右第⼀个 x1 使得 [x1, i]区间内的所有元素的和为 0 。那么 [0, x1 - 1] 区间内的和是不是就是 sum[i] 了。于是问题 就变成：
   • 找到在 [0, i - 1] 区间内，第⼀次出现 sum[i] 的位置即可。 我们不用真的初始化⼀个前缀和数组，因为我们只关心在 i 位置之前，第⼀个前缀和等于 sum[i]的位置。
   因此，我们仅需用⼀个哈希表，⼀边求当前位置的前缀和，一边记录第⼀次出现该前缀和的 位置。
4. 代码示例：

 public int findMaxLength(int[] nums) { Map<Integer, Integer> hash = new HashMap<Integer, Integer>(); hash.put(0, -1); // 默认存在⼀个前缀和为 0 的情况 int sum = 0, ret = 0; for (int i = 0; i < nums.length; i++) { sum += (nums[i] == 0 ? -1 : 1); // 计算当前位置的前缀和 if (hash.containsKey(sum)) ret = Math.max(ret, i - hash.get(sum)); else hash.put(sum, i); } return ret; }

八、矩阵区域和

1. 题目链接：矩阵区域和
2. 题目描述：

给你⼀个 m x n 的矩阵 mat 和⼀个整数 k ，请你返回⼀个矩阵 answer ，其中每个 answer[i][j] 是所有满足下述条件的元素 mat[r][c] 的和：
• i - k <= r <= i + k,
• j - k <= c <= j + k 且
• (r, c) 在矩阵内。
示例 1：
输⼊：mat = [[1,2,3],[4,5,6],[7,8,9]], k = 1
输出：[[12,21,16],[27,45,33],[24,39,28]]
示例 2：
输入：mat = [[1,2,3],[4,5,6],[7,8,9]], k = 2
输出：[[45,45,45],[45,45,45],[45,45,45]]
提示：
m == mat.length
n == mat[i].length
1 <= m, n, k <= 100
1 <= mat[i][j] <= 100

3. 解法：
   算法思路：
   ⼆维前缀和的简单应用题，关键就是我们在填写结果矩阵的时候，要找到原矩阵对应区域的「左上角」以及「右下角」的坐标（推荐大家画图） 左上⻆坐标： x1 = i - k，y1 = j - k ，但是由于会「超过矩阵」的范围，因此需要对 0 取⼀个 max 。因此修正后的坐标为： x1 = max(0, i - k), y1 = max(0, j - k) ; 右下角坐标： x1 = i + k，y1 = j + k ，但是由于会「超过矩阵」的范围，因此需要对 m - 1 ，以及 n - 1 取⼀个 min 。因此修正后的坐标为： x2 = min(m - 1, i + k), y2 = min(n - 1, j + k)
   然后将求出来的坐标代入到「⼆维前缀和矩阵」的计算公式上即可~（但是要注意下标的映射关系）

4. 代码示例：

 public int[][] matrixBlockSum(int[][] mat, int k) { int m = mat.length, n = mat[0].length; // 1. 预处理前缀和矩阵 int[][] dp = new int[m + 1][n + 1]; for (int i = 1; i <= m; i++) for (int j = 1; j <= n; j++) dp[i][j] = dp[i - 1][j] + dp[i][j - 1] - dp[i - 1][j - 1] + mat[i - 1][j - 1]; // 2. 使⽤ int[][] ret = new int[m][n]; for (int i = 0; i < m; i++) for (int j = 0; j < n; j++) { int x1 = Math.max(0, i - k) + 1, y1 = Math.max(0, j - k) + 1; int x2 = Math.min(m - 1, i + k) + 1, y2 = Math.min(n - 1, j + k) + 1; ret[i][j] = dp[x2][y2] - dp[x1 - 1][y2] - dp[x2][y1 - 1] + dp[x1 - 1][y1 - 1]; } return ret; }

结语

本文到这里就结束了，主要介绍了前缀和算法，并解析了几道前缀和算法题目。希望能够对你有帮助。

以上就是本文全部内容，感谢各位能够看到最后，创作不易，希望大家多多支持！

最后，大家再见！祝好！我们下期见！