一维前缀和
前缀和是一种算法
不算精妙
甚至有点暴力
一维前缀和
概念
对于一个长度为 n 的一维数组 (a)
我们将 a[1]-a[i] 的累加和存入 s[i]
从而得到数组 (a) 的前缀数组 (s) :
int a[10]
int s[10];//前缀和数组
s[1]=a[1];
s[2]=a[1]+a[2];
s[3]=a[1]+a[2]+a[3];
... //以此类推用法
前缀和可以很快的求子区间的和
以前缀和相减的形式实现
举个例子，如果我们要求子段 sum(2,4):
sum(a2,a4)=a[2]+a[3]+a[4];
s[1]=a[1];
s[4]=a[1]+a[2]+a[3]+a[4];
s[4]-s[1]=a[2]+a[3]+a[4]=sum(a2,a4);通过这个例子我们可以推出:
sum(l,r)=s[r]-s[l-1]
酱紫就可以方便地求出子区间的和
例题
来看一道题吧！
首先想到暴力枚举
于是开心地发现TLE了
这时，我们可以开心地使用前缀和（然而还是暴力）
预处理一下，然后暴力枚举
code:
#include
using namespace std;
int sum[2560000],n;
int main()
{
scanf("%d",&n);
for (int i=1;i<=n;i++)
{
sum[i]=sum[i-1]+i;
}
for (int i=1;i 然而，我们惊奇地发现，还是T了
于是，我们开始考虑优化：
- 略加思考后，我们发现：当 sum[j]-sum[i]>n 时，所计算的都无用，因为我们要求的是等于 n 的数
- 另外，我们不难发现：当 i 值大于 n 的一半时，无论 j 值是多少，其和都大于 n ，因此当 i>n/2 时，计算也无用
加上优化后，得到如下AC代码：
#include
using namespace std;
int sum[2100000],n;
int main(){
scanf ("%d",&n);
for (int i=1;i<=n;++i)
{
sum[i]=sum[i-1]+i;//前缀和预处理
}
for (int i=1;in)
{
break;//优化1
}
if (sum[j]-sum[i]==n)
{
printf ("%d %d\n",i+1,j);//暴力
}
}
}
return 0;
}