【c++】前缀和教程
今天来讲前缀和
前缀和是什么？
我们先来看一个问题：
读入n和m，读入n个数，接下来m行，每行读入两个数a和b，输出第a个数加到第b个数
输入样例：
5
1 2 3 4 5
2
1 2
3 5
输出样例：
3
12
我们正常会用一个循环，计算从a加到b，但这样子太没有效率了，如果n或m很大，那就回超时了！
那我们要怎么做呢？
定义一个数组b[n+10]={1,3,6,10,15}
仔细观察，b[i]=a[1]+a[2]+a[3]+……+a[i]
比如b[5]=a[1]+a[2]+a[3]+a[4]+a[5]
那这有什么用呢？
如果我们要计算从第三项加到第五项的和，是不是只要用b[5]-b[2]就好了？
b[5]-b[2]
=（a[1]+a[2]+a[3]+a[4]+a[5]）-（a[1]+a[2]）
=a[3]+a[4]+a[5]
这样，我们只用O(1)的时间，就能算出几个数的和，是不是很方便？
这就是前缀和
前缀和怎么写？
知道了原理，写前缀和就很简单了
#include<bits/stdc++.h>
using namespace std;
int main(){
long long n,q,c,d,e;
cin>>n>>q;//n个数,q次询问
long long a[n+10]={},b[n+10]={};
for(int i=1;i<=n;i++){
cin>>a[i];//读入
}
for(int i=1;i<=n;i++){
b[i]=a[i]+b[i-1];//b数组，用来计算
}
for(int i=1;i<=q;i++){
cin>>c>>d;//读入
e=b[d]-b[c-1];//答案
cout<<e<<endl;//输出
}
return 0;
}