以题为例 浅谈前缀和算法

前缀求和算法是什么

前缀和算法就是以空间去换取时间，可用于快速求数组的区间和，它可以用于一维数组和二维数组，但我现在只接触了一维数组并没有接触二维数组，所以在这里先介绍一维数组前缀和相关的知识

前缀和典型代码

	for(int i=1;i<=n;i++){scanf("%d",&t);s[i]=s[i-1]+t;}	

这里一定要求i从1开始计数，当然在这里我们统一的将下表设置为从1开始，具体是要考虑到我们的边界问题，也就是S[1]的求法问题，为了保证我们循环的统一性，我们要将S[0]设置为0，所以我们索性就将下标从1开始设置起，这样也有利于我们后面的初始化，同时也方便了我们的计算；

题例

以题为例见真章

P8649 [蓝桥杯 2017 省 B] k 倍区间

题目链接：[蓝桥杯 2017 省 B] k 倍区间 - 洛谷

题目描述：

给定一个长度为 NN 的数列，A1,A2,⋯ANA1​,A2​,⋯AN​，如果其中一段连续的子序列 Ai,Ai+1,⋯Aj(i≤j)Ai​,Ai+1​,⋯Aj​(i≤j) 之和是 KK 的倍数，我们就称这个区间 [i,j][i,j] 是 KK 倍区间。

你能求出数列中总共有多少个 KK 倍区间吗？

输入格式：

第一行包含两个整数 NN 和 KK(1≤N,K≤105)(1≤N,K≤105)。

以下 NN 行每行包含一个整数 AiAi​(1≤Ai≤105)(1≤Ai​≤105)。

输出格式：

输出一个整数，代表 KK 倍区间的数目。

代码

#include<iostream>
using namespace std;
long long a[100005],b[100005],n,k,c,t;
int main()
{cin>>n>>k;for(int i=1;i<=n;i++){cin>>t;a[i]=a[i-1]+t;}for(int i=0;i<=n;i++){c+=b[a[i]%k]++;}cout<<c<<"";return 0;
}

这里解释一下这道题目，以及代码；

题目的题意就是获取这n个数的连续区间之后是不是k的倍数；

代码解释：首先去求前缀和，这是第一个for循环需要做的；

第二个for循环要做的就是求区间，我当时有个疑问就是为什么这样去求区间，在这里解释一下，当两个数去余同一个数并且余数相同那么这两个数之差就是这个数的倍数如：9和17余8都为1，他们相减就是8是8的倍数；这里还需要注意，他这里是先把b[a[i]%k]的值先赋给c之后在自加的，所以当两个数的余数相同时，只会加一个1；还有注意这个i必需从0开始，因为有的数余数肯定为0，那么这个数就可以是一个区间就要相加；

这道题有第二种解法，但感觉太麻烦，我们直接去求这几个和的差，那么第二个就需要两个for循环增加了时间复杂度

第二种方法代码如下

#include<iostream>
using namespace std;
long long a[100005],b[100005],n,k,c,t;
int main()
{cin>>n>>k;for(int i=1;i<=n;i++){cin>>t;a[i]=a[i-1]+t;}for(int i=0;i<n;i++){for(int j=i+1;j<=n;j++){if((a[j]-a[i])%k==0)c++;}}cout<<c<<"";return 0;
}

交上去被提示时间超时了，所以第二种方法时间复杂度太大了