【模板】前缀和

难度：2星

前缀和模板题。我们定义 $sum[i]sum[i]$ 为前 $ii$ 个数之和，可以通过预处理 $O(n)O(n)$ 求出所有的 $sum[i]sum[i]$，那么查询区间 $[l,r][l,r]$ 中所有数之和只需要输出 $sum[r]-sum[l-1]sum[r]-sum[l-1]$ 即可，每次查询的复杂度为 $O(1)O(1)$ 。

#include<bits/stdc++.h>
using namespace std;
int a[101010];
long long sum[101010];
int main(){
    int n,q,i;
    cin>>n>>q;
    for(i=1;i<=n;i++)cin>>a[i],sum[i]=sum[i-1]+a[i];
    while(q--){
        int l,r;
        cin>>l>>r;
        cout<<sum[r]-sum[l-1]<<endl;
    }
}