题解 | 【模板】静态区间和（前缀和）

这是一道前缀和的基础题。

首先，对于1e6的访问次数，如果每次都使用for循环累加l~r内的数，时间复杂度为O（n^2），于是我们想到要使用(a[i]-a[j-1])表示[j,i]这个区间内的和，只需要在输入的时候预处理数组a就可以了。注意定义数组时要使长度为n+1，防止j=1时越界访问，于是代码如下：

#include <cstdio>
#include <iostream>
#include <bits/stdc++.h>
#include <sstream>
#include <vector>
using namespace std;

int main() {
    int n,q;
    scanf("%d%d",&n,&q);
    vector<long long>a(n+1,0);
    for(int i=1;i<=n;i++){
        scanf("%lld",&a[i]);
        a[i]+=a[i-1];
    }
    stringstream ss;  //使用字符串流输出更快
    for(int i=0;i<q;i++){
        int x,y;
        scanf("%d%d",&x,&y);
        ss<<a[y]-a[x-1]<<"\n";
    }
    printf("%s",ss.str().c_str());
    return 0;
}