题目描述
AcWing 795.前缀和
这道题用前缀和的方法,将时间复杂度从O(n^2)减少到O(n),比较easy,具体做法详见下文
样例
cin>>
5 3
2 1 3 6 4
1 2
1 3
2 4
cout<<
3
6
10
算法1
(前缀和) $O(n)$
用tmp数组,另开一个前缀和数组,用来记录前面n个数字之和,只需要tmp[i] = tmp[i - 1] + number[i];即可。需要注意的是要从1–n而不是0–n-1,理由是需要tmp[0] = 0(自己体会)。
当计算从left到right的和就可以用tmp[right] - tmp[left - 1]了,这个就很简单了。
时间复杂度
参考文献
https://www.acwing.com/activity/content/code/content/3789828/
C++ 代码
#include<bits/stdc++.h>
using namespace std;
const int N = 1e5 + 10;
int number[N], tmp[N];
int main(void){
int n, m;
cin >> n >> m;
for(int i = 1; i <= n; i++) cin >> number[i];
for(int i = 1; i <= n; i++) tmp[i] = tmp[i - 1] + number[i];
while(m--){
int left, right;
cin >> left >> right;
cout << tmp[right] - tmp[left - 1] << endl;
}
return 0;
}