前缀和
前缀和是什么
可以说，前缀和是一种优化程序运行时间的一种方法，一般用于求一个序列中的区间和。
前缀和的原理
顾名思义，前缀和数组，即一个序列中前 \(i\) 个数据之和。
\[b_i = \sum_{j = 0}^{i} a_j \]所以 \(a_l\) 到 \(a_r\) 的和是：
\[\sum_{j = l}^{r} a_j = b_r - b_{l - 1} \]难么该如何将求前缀和的时间复杂度降到 \(O(n)\) 呢？
\[b_i = b_{i-1} + a_i \text{ （这里的 } i \text{ 是下标从 } 1 \text{ 开始的数）} \]题目
例题 1 （P8218 求区间和）
输入 / 输出：
# input
5
1 2 3 4 5
4
1 2
1 5
2 3
3 5
# Output
1 3 6 10 15
3
15
5
12
本题是前缀和模板，不做解释。
Code
#include <iostream>
using namespace std;
#define MAXN 100005
int a[MAXN],b[MAXN];
int main()
{
int n;
cin>>n;
for(int i=1;i<=n;i++){
cin>>a[i];
b[i]=b[i-1]+a[i];
}
for(int i=1;i<=n;i++) cout<<b[i]<<" ";//输出前缀和数组
cout<<endl;
int q;
cin>>q;
while(q--){//询问 q 次
int l,r;
cin>>l>>r;
cout<<b[r]-b[l-1]<<endl;
}
return 0;
}
练习 1（P10233 dx 分计算）
练习 2（P1115 最大子段和）
各题代码
Code - 练习 1
#include <iostream>
using namespace std;
#define MAXN 10000005
int b[MAXN];
int main()
{
int t;
cin>>t;
while(t--)
{
string s;
cin>>s;
if(s[0]=='P') b[0]=3;
if(s[0]=='p') b[0]=2;
if(s[0]=='G') b[0]=1;
if(s[0]=='g'||s[0]=='m') b[0]=0;
for(int i=1;i<s.size();i++)
{
if(s[i]=='P') b[i]=3+b[i-1];
if(s[i]=='p') b[i]=2+b[i-1];
if(s[i]=='G') b[i]=1+b[i-1];
if(s[i]=='g'||s[i]=='m') b[i]=b[i-1];
}
int q;
cin>>q;
while(q--)
{
int l,r;
cin>>l>>r;
if(l==1) cout<<b[r-1]<<endl;
else cout<<b[r-1]-b[l-2]<<endl;
}
}
return 0;
}
Code - 练习 2
#include <iostream>
using namespace std;
#define MAXN 200005
int f[MAXN];
int main()
{
int n;
cin>>n;
int x;
cin>>x;
f[0]=x;
for(int i=1;i<n;i++)
{
int temp;
cin>>temp;
f[i]=max(f[i-1]+temp,temp);
}
int maxans=-1e9;
for(int i=0;i<n;i++)
{
maxans=max(maxans,f[i]);
}
cout<<maxans;
return 0;
}