2516 区间求和(前缀和例题)
小于 1 分钟
2516 区间求和(前缀和例题)
【算法】 前缀和
【C++】 一维数组、前缀和、scanf/printf
【难度】 入门
一、题目简述
个数的序列, 次询问,每次询问第 到第 项的数字和。,。
二、解题思路
高达 ,如果每次询问都循环累加,复杂度 会超时。必须用前缀和优化到 。
核心公式:sum[l..r] = pre[r] - pre[l-1]
由于数据大,建议用 scanf/printf 代替 cin/cout(或用 ios::sync_with_stdio(false))。
三、参考代码
#include <bits/stdc++.h>
using namespace std;
const int N = 1e6 + 5;
long long pre[N]; // 前缀和可能超 int
int main() {
int n, k;
scanf("%d%d", &n, &k);
for (int i = 1; i <= n; i++) {
int x;
scanf("%d", &x);
pre[i] = pre[i - 1] + x;
}
while (k--) {
int l, r;
scanf("%d%d", &l, &r);
printf("%lld\n", pre[r] - pre[l - 1]);
}
return 0;
}四、复杂度分析
- 时间:
- 空间:
五、易错点
- 用
long long,因为 在 int 范围内,但多次累加前缀和可能超。 - 大数据必须用
scanf/printf,cin/cout会超时。
