基本思想
前缀和数组就是一个数组的前i项和
前缀和的用处：前缀和数组求出来之后我们就可以就可以求数组中的某个特定区间的和
就比如说求l到R的和，我们可以转换为求1到R的和减去1到l-1的和
接下来我们来做两道题，让大家感受一下
1.前缀和
这道题是一道非常经典最能代表前缀和算法的一道题
这道题的思路很简单就是根据公式s[i]=s[i-1] a[i]然后将前缀和求出来，根据条件去输出，我们来看一下代码
#include<iostream>
using namespace std;
#define N 100010
//n个数据和m行
int n,m;
//定义一个数组和一个前缀和数组
int a[N],S[N];
//定义两个边界
int l,r;
int main()
{
//输入
cin>>n>>m;
//输入
for(int i=1;i<=n;i )cin>>a[i];
//将前缀和的s[0]定义为0，这样方便求出第多少到第多少的和
S[0]=0;
//根据公式求出前缀和
for(int i=1;i<=n;i )
{
S[i]=S[i-1] a[i];
}
//根绝条件输出
while(m)
{
cin>>l>>r;
cout<<S[r]-S[l-1]<<endl;
m--;
}
return 0;
}2.子矩阵的和
这道题是二维的前缀和，我们先来讨论一下二维数组的前缀和的基本概念
对于二维数组的前缀和我们先看下图颜色标出的方块的区间
上面这个蓝色的区域就是二维数组的前缀和，这下我们来讨论我们该怎么求这个前缀和
深色区域就表示S[i-1,j]
紫色区域是S[i,j-1]，从上图不难看出中间的四个方形的区域被重复加了两次，意思说我们还要减去中间的四个方形的区域
减去黑色区域，加上红色区域最后就得到了前缀和
**公式：S[i,j]=S[i-1,j] S[i,j-1]-S[i-1,j-1] a[i,j]
那么下面的阴影区域怎么求呢？
我们可以先求S[x1,y1]
减去紫色区域
再减去深蓝色区域
因为左上角的深蓝色区域被减了两次，所以需要加上，最后便得到了原来的浅蓝色区域
公式：S=S[x1,y1]-S[x2-1,y1]-S[x1,y2-1] S[x2-1,y2-1]
接下来我们直接来做上面的子矩阵的和，根据上面的公式可以直接写出代码
代码语言：javascript复制#include<iostream>
using namespace std;
#define N 1010
int n,m,q;
int a[N][N],s[N][N];
int main()
{
cin>>n>>m>>q;
for(int i=1;i<=n;i )
{
for(int j=1;j<=m;j )
{
cin>>a[i][j];
}
}
for(int i=1;i<=n;i )
{
for(int j=1;j<=m;j )
{
s[i][j]=s[i-1][j] s[i][j-1]-s[i-1][j-1] a[i][j];
}
}
while(q--)
{
int x1,x2,y1,y2;
cin>>x1>>y1>>x2>>y2;
cout<<s[x2][y2]-s[x1-1][y2]-s[x2][y1-1] s[x1-1][y1-1]<<endl;
}
return 0;
}3.长度最小的子数组
根据题目描述，我们可以先求出前缀和，然后用滑动窗口去更新每一次的最小的长度
代码语言：javascript复制int minSubArrayLen(int target, int* nums, int numsSize) {
int *S=(int*)malloc(sizeof(int)*(numsSize 1));
S[0] = 0;
for (int i = 1;i <= numsSize;i )
{
S[i] = S[i - 1] nums[i - 1];
}
int min = 0;
int l = 0;
int r = 1;
while (r < numsSize 1)
{
if (l == r)
{
if (S[l] >= target)
{
if (min > l || min == 0)
min = l;
}
r ;
}
else
{
if (S[r] - S[l] >= target)
{
if (min > r - l || min == 0)
{
min = r - l;
}
l ;
}
else {
r ;
}
}
}
return min;
}4，除自身以外数组的乘积
这道题需要排除特殊情况，特殊情况就是0，遇到零我们直接跳过，然后求出累乘，求出累乘之后，再开辟一个数组，用这个数组去存储除自身以外的所有数的乘积，首先我们需要记录一下零的个数，如果零的个数超过两个的话，数组中所有的数都会被置为零，当只有一个零的时候，除了零之外的数都是0,0对应的乘积就是剩下的数的乘积 代码展示
代码语言：javascript复制int* productExceptSelf(int* nums, int numsSize, int* returnSize) {
//累乘
int sum = 1;
//记录零的个数
int count = 0;
for (int i = 0;i < numsSize;i )
{
//不等于0就乘到累乘中
if (nums[i] != 0)
{
sum *= nums[i];
}
//如果是0就count
if (nums[i] == 0)
{
count ;
}
}
//将*returnSize的大小用数组大小赋值
*returnSize = numsSize;
//创建空间
int* newnode = (int*)malloc(sizeof(int) * (*returnSize));
if (count >= 2)
{
for (int i = 0;i < (*returnSize);i )
{
newnode[i] = 0;
}
}
else if (count == 0)
{
for (int i = 0;i < (*returnSize);i )
{
newnode[i] = sum / nums[i];
}
}
else
{
for (int i = 0;i < (*returnSize);i )
{
if (nums[i] == 0)
{
newnode[i] = sum;
}
else
{
newnode[i] = 0;
}
}
}
return newnode;
}总结
在本文中，我们深入探讨了前缀和算法的原理、应用以及实现方式。通过对前缀和的定义和性质的理解，我们可以更有效地解决一系列问题，特别是那些涉及连续子数组和区间求和的场景。通过将原始数据预处理成前缀和数组，我们能够在常数时间内快速地回答各种查询，从而大大提高了算法的效率。
我们讨论了如何应用前缀和算法解决了几个实际问题，例如求解子数组和的最大值、最小值，以及计算区间和等。这些问题在实际应用中经常遇到，而前缀和算法为我们提供了一种高效的解决方案。
此外，我们还介绍了如何通过巧妙地利用前缀和数组，解决了一些其他类型的问题，例如寻找具有特定和值的子数组个数、寻找具有特定和值的子数组的起始位置等。
总的来说，前缀和算法是一种非常强大且实用的技术，可以广泛应用于解决各种问题，包括算法竞赛、编程面试以及实际工程项目中。通过深入理解前缀和算法的原理和应用，我们可以在算法设计和问题求解中发挥更大的作用，提高代码的效率和性能。希望本文对读者对前缀和算法有所启发，并能够在实践中加以运用。
