因为作者报名了蓝桥杯最近在刷算法，分享一下最近学到的一些比较经典的题型，第一个就是前缀和，这里我将讲解一下一维前缀和二维前缀和
一维前缀和：
概念和定义：
前缀和，也称为累积和，是一个数组，其中每个元素是原数组从开始到该位置所有元素的总和，
- 前缀和是一种算法技术，用于高效计算数组子段的和。
- 它通过预计算累积和数组，在O(1)时间内回答范围和查询。
应用场景：
前缀和的主要应用是范围和查询。例如，要计算数组从索引m到n的和：
- 如果m=0，答案是prefix_sum[n]。
- 如果m>0，答案是prefix_sum[n] - prefix_sum[m-1]。 这在O(1)时间内完成，特别适合处理多个查询。
例如，在[1, 2, 3, 4]中：
- 从索引1到2的和是6 - 1 = 5（元素2+3）。
- 从索引0到3的和是10。
算法思想：
- 创建一个与原数组相同大小的新数组prefix_sum。
- 设置prefix_sum[0] = arr[0]。
- 对于索引i从1到n-1，设置prefix_sum[i] = prefix_sum[i-1] + arr[i]。 时间复杂度为O(n)，空间复杂度为O(n)。
题目类型讲解 ：
题目链接：求区间和 - 洛谷
这个题目意思很简单，这里我再和大家简单说一下，通过这个题目我们就明白是什么意思了，就很简单，让求一个数组的区间和
关于输入案例当中的解释：
4 数组长度
长度为4的自输入数组4 3 2 1
2就是下面有两个区间需要我们求
1 4 就是1-4区间的和
2 3 就是2-3区间的和
知道了需求，大家在学前缀和之前遇到这个题第一个想到的估计就是暴力求解了，直接套两层for循环，外面是区间的个数，里面遍历从区间几到几的一个和，但是这样非常耗时，所以就来到了我们的前缀和算法求解思路，通过上面的讲解相信大家已经有所思路了，那我这里通过代码简单简洁一下啦~
c++代码：
1.定义前缀和数组并进行初始化：
vector<int> newArr(n+1,0);
for(int i=1;i<=n;i++){
newArr[i]=arr[i-1]+newArr[i-1];
}2.输入区间并进行区间求和操作：
int m,a,b;
cin>>m;
while(m--){
cin>>a>>b;
cout<<newArr[b]-newArr[a-1]<<endl;
}总代码：
#include<bits/stdc++.h>
using namespace std;
int main(){
int n=0;
cin>>n;
vector<int> arr(n,0);
for(int i=0;i<n;i++){
cin>>arr[i];
}
vector<int> newArr(n+1,0);
for(int i=1;i<=n;i++){
newArr[i]=arr[i-1]+newArr[i-1];
}
int m,a,b;
cin>>m;
while(m--){
cin>>a>>b;
cout<<newArr[b]-newArr[a-1]<<endl;
}
return 0;
}
二维前缀和：
二维数组的前缀和比一维数组的麻烦一下
概念和定义：
二维前缀和（也称为二维累积和）是算法领域中一个重要的技术，特别在处理矩阵子矩阵和查询时表现出色
对于一个大小为 m x n 的矩阵 A，二维前缀和矩阵 P 是这样一个矩阵，其中 P[i][j] 表示从 A[0][0] 到 A[i-1][j-1] 的所有元素的总和。形式上：
这类似于一维前缀和的扩展，但需要处理二维空间中的重叠计算。
应用场景：
二维前缀和的主要应用是高效回答子矩阵和查询
算法思想：
计算二维前缀和矩阵的步骤如下：
- 假设我们的矩阵A的长宽分别为m n
- 创建一个大小为 (m+1) x (n+1) 的矩阵P（初始化前缀的矩阵，从（0，0）到（i，j）之间的矩阵和），初始化的首行和首列为0，以处理边界情况。
- 对于每个 i 从1到m，j 从1到n
- 计算： P[i][j]=A[i−1][j−1]+P[i−1][j]+P[i][j−1]−P[i−1][j−1]P[i][j] = A[i-1][j-1] + P[i-1][j] + P[i][j-1] - P[i-1][j-1]P[i][j]=A[i−1][j−1]+P[i−1][j]+P[i][j−1]−P[i−1][j−1] 这个公式的推导基于包含-排除原理：P[i-1][j] 是从 (0,0) 到 (i-1,j) 的和，P[i][j-1] 是从 (0,0) 到 (i,j-1) 的和，但 (0,0) 到 (i-1,j-1) 的部分被重复计算了两次，因此需要减去 P[i-1][j-1]，然后加上当前元素 A[i-1][j-1]。
大家上面P矩阵的初始化如果看不懂可以看上面那张图，就是说坐标为(x4,y4)的前缀和为(x3,y3)的前缀和加上（x2,y2）前缀和然后减去（x1,y1）处的前缀和
示例计算：
创建矩阵A：
初始化 P 为3x3，首行首列为0：
- P[1][1] = A[0][0] + P[0][1] + P[1][0] - P[0][0] = 1 + 0 + 0 - 0 = 1
- P[1][2] = A[0][1] + P[0][2] + P[1][1] - P[0][1] = 2 + 0 + 1 - 0 = 3
- P[2][1] = A[1][0] + P[1][1] + P[2][0] - P[1][0] = 3 + 1 + 0 - 0 = 4
- P[2][2] = A[1][1] + P[1][2] + P[2][1] - P[1][1] = 4 + 3 + 4 - 1 = 10
最终 P 为：
查询子矩阵和：
使用前缀和矩阵，可以在O(1)时间内计算任意子矩阵的和。例如，计算从 (0,0) 到 (1,1) 的子矩阵和：
sum = P[2][2] - P[0][2] - P[2][0] + P[0][0] = 10 - 0 - 0 + 0 = 10 这与手动计算 1 + 2 + 3 + 4 = 10 一致。
另一个例子，从 (1,0) 到 (1,1)：
sum = P[2][2] - P[1][2] - P[2][0] + P[1][0] = 10 - 3 - 0 + 0 = 7 对应 3 + 4 = 7，正确。
题目类型讲解：
题目链接：最大加权矩形 - 洛谷
代码：
初始化前缀和数组：
// 构建前缀和数组（尺寸(n+1)x(n+1)，0行0列初始化为0）
vector<vector<int> > sum(n + 1, vector<int>(n + 1, 0));
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= n; j++) {
sum[i][j] = sum[i - 1][j] + sum[i][j - 1] - sum[i - 1][j - 1] + nums[i - 1][j - 1];
}
}遍历子矩阵：
上面有子矩阵的示例讲解，这里我就不过多赘述了，和上面的一样
for (int x1 = 1; x1 <= n; x1++) {
for (int y1 = 1; y1 <= n; y1++) {
for (int x2 = x1; x2 <= n; x2++) {
for (int y2 = y1; y2 <= n; y2++) {
int current = sum[x2][y2] - sum[x1 - 1][y2] - sum[x2][y1 - 1] + sum[x1 - 1][y1 - 1];
res = max(res, current);
}
}
}
}总代码：
#include <bits/stdc++.h>
using namespace std;
int main() {
int n;
cin >> n;
vector<vector<int> > nums(n, vector<int>(n));
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
cin >> nums[i][j];
}
}
// 构建前缀和数组（尺寸(n+1)x(n+1)，0行0列初始化为0）
vector<vector<int> > sum(n + 1, vector<int>(n + 1, 0));
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= n; j++) {
sum[i][j] = sum[i - 1][j] + sum[i][j - 1] - sum[i - 1][j - 1] + nums[i - 1][j - 1];
}
}
int res = nums[0][0];
// 遍历所有可能的子矩阵
for (int x1 = 1; x1 <= n; x1++) {
for (int y1 = 1; y1 <= n; y1++) {
for (int x2 = x1; x2 <= n; x2++) {
for (int y2 = y1; y2 <= n; y2++) {
int current = sum[x2][y2] - sum[x1 - 1][y2] - sum[x2][y1 - 1] + sum[x1 - 1][y1 - 1];
res = max(res, current);
}
}
}
}
cout << res << endl;
return 0;
}
over ！！！