題目描述
給定?n?個正整數組成的數列?a1?,a2?,?,an??和?m?個區間?[li?,ri?]，分別求這?m?個區間的區間和。
輸入格式
第一行，為一個正整數?n?。
第二行，為?n?個正整數?a1?,a2?,?,an?
第三行，為一個正整數?m?。
接下來?m?行，每行為兩個正整數?li?,ri??，滿足?1≤li?≤ri?≤n
輸出格式
共?m?行。
第?i?行為第?i?組答案的詢問。
輸入輸出樣例
輸入 #1
4 4 3 2 1 2 1 4 2 3
輸出 #1
10 5
說明/提示
樣例解釋：第 1 到第 4 個數加起來和為 10。第 2 個數到第 3 個數加起來和為 5。
對于?50%?的數據：n,m≤1000?；
對于?100%?的數據：1≤n,m≤，1≤ai?≤
。
暴力只能得40%，要用前綴和優化
#include<iostream>
using namespace std;int n, m;
const int N = 1e5+10;
int a[N];int main()
{ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);cin>>n;for(int i=1; i<=n; ++i){cin>>a[i];a[i] += a[i-1]; //前綴和 }cin>>m;while(m--){int r, l;cin>>r>>l;int ans = 0;ans = a[l]-a[r-1];cout<<ans<<'\n';}return 0;
}
