P76026 区间求和 — 题解

专题： 前缀和
适用题目： 新生 OJ 本地题包中的 P76026，不要直接用于外站同名题。

解题思路

令 pre[i] 为前 i 个数之和，则区间和为 pre[r]-pre[l-1]。

复杂度

预处理 $O(n)$，每次查询 $O(1)$，空间 $O(n)$。

易错点

数组元素和可能超过 32 位整数，使用 long long。

C11 参考程序

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <ctype.h>
#include <limits.h>

int main(void) {
    int n,q;scanf("%d%d",&n,&q);long long *pre=calloc(n+1,sizeof(long long));
    for(int i=1;i<=n;i++){long long x;scanf("%lld",&x);pre[i]=pre[i-1]+x;}
    while(q--){int l,r;scanf("%d%d",&l,&r);printf("%lld\n",pre[r]-pre[l-1]);}
    free(pre);return 0;
}

C++17 参考程序

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define nl '\n'

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n,q;
    cin>>n>>q;
    vector<ll>pre(n+1);
    for(int i=1;i<=n;i++){
        ll a;
        cin>>a;
        pre[i]=pre[i-1]+a;
    }
    while(q--){
        int l,r;
        cin>>l>>r;
        cout<<pre[r]-pre[l-1]<<nl;
    }
    return 0;
}

题解建议设置为训练结束后开放。普通判题无法验证是否实际使用指定函数或 STL。