A468.区间求和

暴力for循环累加,如果数据稍微大一点，就会超时，AC代码⬇

#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 5;
int num[N];
int main(){
    int n,m;
    cin >> n >> m;
    for(int i = 1;i <= n;i++){
        cin >> num[i];
    }
    for(int i = 1;i <= m;i++){
        int x,y,sum = 0;
        cin >> x >> y;
        for(int i = x;i <= y;i++){
            sum += num[i];
        }
        cout << sum << endl;
    }
    return 0;
}

前缀和写法,数据大不会超时,AC代码⬇

#include <bits/stdc++.h>
using namespace std;
int x[1000005];
int main(){
    int n,m,l,r;
    cin >> n >> m;
    for(int i = 1;i <= n;i++){
    	cin >> x[i];
        x[i] += x[i-1];
    }
    while(m--){
    	cin >> l >> r;
        cout << x[r] - x[l - 1] << endl;
    }
    return 0;
}