2129 区间和
小于 1 分钟
2129 区间和
【算法】 前缀和
【C++】 一维数组、前缀和
【难度】 入门
一、题目简述
给定 个正整数(,每个数 ),以及 ,求第 到第 个数字的和。
二、解题思路
很小,可以直接循环累加。但推荐用前缀和:pre[i] = pre[i-1] + a[i],则区间和 = pre[r] - pre[l-1]。单次查询 。
手动模拟:[1,2,3,4,5],l=2, r=3 → pre[3]-pre[1] = 6-1 = 5。
三、参考代码
#include <bits/stdc++.h>
using namespace std;
int main() {
int n;
cin >> n;
int a[105], pre[105] = {0};
for (int i = 1; i <= n; i++) {
cin >> a[i];
pre[i] = pre[i - 1] + a[i];
}
int l, r;
cin >> l >> r;
cout << pre[r] - pre[l - 1] << endl;
return 0;
}四、复杂度分析
- 时间: 建前缀和 + 查询
- 空间:
