🎬 个人主页：谁在夜里看海.
⛰️ 一念既出，万山无阻
目录
📚一、算法思想
前缀和算法是一种常用的算法技巧，用于快速计算数组中某个区间的元素总和。假设我们有一个数组，需要频繁地求其中某一个区间的和，那么每一次都需要遍历求和，当中是有很多重复计算的。假设我们先求的是 [2,4] 区间的和，然后需要求 [2,5] 区间，后者的运算是可以利用前者的运算结果的，但是我们并没有将前者的结果进行保存，所以 [2,4] 这个区间还是要重复计算一遍，我们进行n次计算就要遍历n次数组，这当中是有很多重复工作的。
前缀和数组就完美解决了这一问题，在求区间和之间，先预处理一个前缀和数组，每一个元素表示前缀区间的和，而我们要求中间某一区间的和时，只需找到区间的首元素和尾元素，用尾元素的前缀和减去首元素的前缀和，就是所要的结果，这样只需要进行一次遍历，就可以求出任意区间的和，减去了不必要的重复运算。
📖一维前缀和
假设我们有一个数组 a，它的前缀和数组 sum 定义为：sum[i]=a[0]+a[1]+⋯+a[i−1](i≥1)
简单来说，前缀和数组的每个元素表示从数组起点到当前位置的累计和。
通过前缀和，我们可以快速计算数组中任意区间 [i,j] 的和：sum([i,j])=p[j+1]−p[i]
这样，避免了重复遍历区间内的元素。
❗️注意：
由于求区间 [i,j] 时是用 j的前缀和 - (i-1)的前缀和，所以在构建前缀和数组的时候，需要在首位置插入一个0元素，避免数组越界的情况发生：
📖二维前缀和
对于二维数组，我们也可以使用类似的前缀和技巧来快速计算矩阵中任意子矩形的和。
假设我们有一个二维数组 a 的大小为 m×n，其前缀和数组 sum 定义为：
sum[i][j]=从 (0,0) 到 (i−1,j−1) 的元素总和
通过构建二维前缀和数组，可以快速计算任意子矩形 [i1,j1] 到 [i2,j2] 的和：
sum([i1,j1] 到 [i2,j2]) = sum[i2+1][j2+1] - sum[i1][j2+1] - sum[i2+1][j1] + sum[i1][j1]
❗️注意：
同样地，在二维前缀和数组中，需要为每一行和每一列插入 0，避免数组越界。
📚 二、具体运用
1.【模板】前缀和
难度等级：⭐⭐⭐
题目链接：【模板】前缀和_牛客题霸_牛客网
题目描述：
描述
给定一个长度为n的数组a1,a2,....an.
接下来有q次查询, 每次查询有两个参数l, r.
对于每个询问, 请输出al+a(l+1)+....+ar
输入描述：
第一行包含两个整数n和q.
第二行包含n个整数, 表示a1,a2,....an.
接下来q行,每行包含两个整数 l和r.
输出描述：
输出q行,每行代表一次查询的结果.
示例1
输入：
3 2 1 2 4 1 2 2 3输出：
3 6
简单来说，题目要求对一个数组，多次求其中某一区间的和，对于这种频繁求取区间和的问题，我们可以先预处理一个前缀和进行求解
算法思路
① 先预处理一个前缀和数组：
用 sum[i] 表示：[1,i] 区间内所有元素的和，sum[i-1] 里面存的就是 [1,i-1] 区间内所有元素的和，那么根据递推公式：sum[i] = sum[i-1] +arr[i]；
② 使用前缀和数组，快速求出某一区间内所有元素的和：
当求取的区间是 [i,j] 时，区间内元素和为：sum[j] - sum[i-1] 。
代码
#include <iostream>
#include <vector>
using namespace std;
int main() {
int n,q;
cin >> n >> q;
vector<int> arr(n+1);
for(int i=1;i < n+1;++i)
cin >> arr[i];
vector<long long> sum(n+1);
for(int i=1;i < n+1;++i)
sum[i] = sum[i-1] + arr[i];
int l,r;
while(q--)
{
cin >> l >> r;
cout << sum[r]-sum[l-1] << endl;
}
return 0;
}2.【模板】⼆维前缀和
难度等级：⭐⭐⭐⭐
题目链接：【模板】二维前缀和_牛客题霸_牛客网
题目描述：
给你一个 n 行 m 列的矩阵 A ，下标从1开始。
接下来有 q 次查询，每次查询输入 4 个参数 x1 , y1 , x2 , y2
请输出以 (x1, y1) 为左上角 , (x2,y2) 为右下角的子矩阵的和，输入描述：
第一行包含三个整数n,m,q.
接下来n行，每行m个整数，代表矩阵的元素
接下来q行，每行4个整数x1, y1, x2, y2，分别代表这次查询的参数示例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
这是一道二维数组的问题，我们需要频繁地在一个二维数组中求子矩阵的元素和，和一维数组一样，也可以利用前缀和进行求解
算法思路
类⽐于⼀维数组的形式，如果我们能处理出来从元素的累加和，就可以在 [0, 0] 位置到 [i, j] 位置这⽚区域内所有 O(1) 的时间内，搞定矩阵内任意区域内所有元素的累加和：
① 与⼀维数组类似，我们要在矩阵的最上⾯和最左边添加上⼀⾏和⼀列 0，这样我们就可以省去⾮常多的边界条件的处理：
这样，我们填写前缀和矩阵数组的时候，下标直接从1开始，就不用担心越界了。
② 递推前缀和矩阵：
红色部分就是我们要求的前缀和矩阵，我们在求和的时候可以利用之前已经求得的矩阵，用蓝色区域+橙色区域减去重合的黄色区域再加上剩下的一小块红色区域就是最终结果了：
③ 使用前缀和矩阵
我们要求的是中间某一矩阵的和（绿色部分），我们只需用红色部分-蓝色部分-橙色部分+重合的黄色部分，最终结果就是所求的绿色部分。
代码
#include <iostream>
using namespace std;
#include <vector>
int main() {
int n,m,q;
cin>>n>>m>>q;
vector<vector<int>> number(n+1,vector<int>(m+1,0));
for(int i=1;i<=n;++i)
for(int j=1;j<=m;++j)
cin>>number[i][j];
vector<vector<long long>> sum(n+1,vector<long long>(m+1,0));
for(int i=1;i<=n;++i)
for(int j=1;j<=m;++j)
sum[i][j]=sum[i-1][j]+sum[i][j-1]+number[i][j]-sum[i-1][j-1];
int x1,y1,x2,y2;
while(q--)
{
cin>>x1>>y1>>x2>>y2;
cout<<sum[x2][y2]-sum[x2][y1-1]-sum[x1-1][y2]+sum[x1-1][y1-1]<<endl;
}
return 0;
}3.和为k的子数组
难度等级：⭐⭐⭐⭐
题目链接：560. 和为 K 的子数组 - 力扣（LeetCode）
题目描述：
给你一个整数数组
nums和一个整数k，请你统计并返回 该数组中和为k的子数组的个数 。子数组是数组中元素的连续非空序列。
示例 1：
输入：nums = [1,1,1], k = 2 输出：2示例 2：
输入：nums = [1,2,3], k = 3 输出：2
算法思路
设 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 。因此，我们仅需⽤⼀个哈希表，⼀边求当前位置的前缀和，⼀边存下之前每⼀种前缀和出现的次数。
代码
class Solution {
public:
int subarraySum(vector<int>& nums, int k) {
int cur=0,target=0,ret=0;
unordered_map<int,int> map;
++map[0];
for(int i=0;i<nums.size();++i)
{
cur+=nums[i];
target = cur-k;
if(map.count(target)>0)
ret+=map[target];
++map[cur];
}
return ret;
}
};4.矩阵区域和
难度等级：⭐⭐⭐⭐
题目链接：560. 和为 K 的子数组 - 力扣（LeetCode）
题目描述：
给你一个
m x n的矩阵mat和一个整数k，请你返回一个矩阵answer，其中每个answer[i][j]是所有满足下述条件的元素mat[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]]
算法思路
这道题目的意思是，给你一个二维数组，让我们求出数组中每一个元素向外延伸长度k的矩阵的和，例如：下标为（0,0）的元素向外延伸长度1的矩阵的和就应该是（0,0）到（1,1）的矩阵的和
而下标为（1,1）的元素向外延伸长度1的矩阵的和就应该是（0,0）到（2,2）的矩阵的和
这是一道二维矩阵和的具体运用。
代码
class Solution {
public:
vector<vector<int>> matrixBlockSum(vector<vector<int>>& mat, int k) {
int m=mat.size();
int n=mat[0].size();
vector<vector<int>> sum(m+1,vector<int>(n+1,0));
for(int i=0;i<m;++i)
for(int j=0;j<n;++j)
sum[i+1][j+1]=sum[i][j+1]+sum[i+1][j]+mat[i][j]-sum[i][j];
vector<vector<int>> ret(m,vector<int>(n));
int x1,y1,x2,y2;
for(int i=0;i<m;++i)
{
for(int j=0;j<n;++j)
{
x1=max(1,i-k+1); y1=max(1,j-k+1);
x2=min(m,i+k+1); y2=min(n,j+k+1);
ret[i][j]=sum[x2][y2]-sum[x1-1][y2]-sum[x2][y1-1]+sum[x1-1][y1-1];
}
}
return ret;
}
};📚三、总结
前缀和算法通过预处理一个前缀和数组来避免重复计算，快速求解数组中任意区间的和。在一维情况下，前缀和数组存储从数组起点到当前位置的累计和，从而能够高效地计算区间和；在二维情况下，通过构建二维前缀和数组，可以快速计算矩阵中任意子矩形的和。
以上就是【优选算法篇·第四章：前缀和】的全部内容，欢迎指正~
码文不易，还请多多关注支持，这是我持续创作的最大动力！