描述

给定一个长度为$nn$的数组，一共有$qq$个询问，每次询问区间$[l,r][l,r]$的和

思路

• 前缀和的模板题，设$sum[n]sum[n]$表示区间$[1,n][1,n]$的和，则每次询问输出$sum[r]-sum[l-1]sum[r]-sum[l-1]$即可

代码

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MAXN=1e5+5;
ll sum[MAXN];

int main()
{
    int n,q;
    scanf("%d%d",&n,&q);
    for(int i=1;i<=n;i++)
        scanf("%lld",&sum[i]);
    for(int i=1;i<=n;i++)
        sum[i]+=sum[i-1];
    while(q--)
    {
        int l,r;
        scanf("%d%d",&l,&r);
        printf("%lld\n",sum[r]-sum[l-1]);
    }
}

时间复杂度$O(n+q)O(n+q)$，空间复杂度$O(n)O(n)$