【題目敘述】https://zerojudge.tw/ShowProblem?problemid=a693
【方法-1】一般做法 (TLE)
#include <iostream>
using namespace std;
int main() {
int n, m;
while (cin >> n >> m) {
int a[n];
for (int i = 0; i < n; i++) {
cin >> a[i];
}
for (int i = 0; i < m; i++) {
int l, r;
cin >> l >> r;
l--; //改成 0-based
r--; //改成 0-based
int sum = 0;
for (int j = l; j <= r; j++) {
sum += a[j];
}
cout << sum << "\n";
}
}
return 0;
}
【方法-2】前綴和
#include <iostream>
using namespace std;
int main() {
int n, m;
while (cin >> n >> m) {
int x, ps[n+1];
ps[0] = 0;
for (int i = 1; i <= n; i++) {
cin >> x;
ps[i] = ps[i-1] + x; //前綴和
}
for (int i = 0; i < m; i++) {
int l, r;
cin >> l >> r;
cout << ps[r] - ps[l-1] << "\n";
}
}
return 0;
}