一维前缀和-知识总结 一维前缀和概念 一维前缀和（Prefix Sum）是一种常见的数据处理技术，特别适用于高效计算数组某一段区间的和。它通过预处理数组，使得在进行区间和查询时能快速得到结果，从而避免了重复计算。
一维前缀和计算方法 假设有一个数组array，长度为n。我们定义一个前缀和数组prefixsum，其长度也是n，使prefixsum[i]表示数组array从第1个元素到第i个元素的所有元素之和。利用递推公式求prefix_sum的值。
递推公式如下： prefixsum[i] = prefixsum[i-1] + array[i]
代码示例如下：
prefix[0] = 0;
for (int i = 0; i < n; ++i) {
prefix[i] = prefix[i - 1] + arrary[i];
}算法评价 时间复杂度：O(n) 空间复杂度：O(n)
一维前缀和应用 求一维数组任意区间和方法 若已知数组array和该数组的前缀prefix_sum，计算任意区间的区间和时只需要知道区间起点和终点，即可在O(1)的时间内计算其区间和。
代码示例：
int l = 1; // 区间起点
int r = 3; // 区间终点
int sum_lr = prefix_sum[r] - prefix_sum[l - 1]求数组中具有最大和的连续子段和 利用maxsubsum变量记录到达当前点i时的最大子段和 利用min_prefix变量记录到达当前点i时的最小前缀和 求和方式：
for (int i = 1; i <= n; ++i) {
max_sub_sum = max(prefix[i] - min_prefix, max_sub_sum);
min_prefix = min(prefix[i], min_prefix);
}· 以下内容需要学习过计数排序后再来阅读 · 计数排序 在技术排序中，利用前缀和和后缀和作为辅助统计数组用以在O(1)的时间内查询到一个数值的排序位置。
计数排序从小到大排序代码
1#include <bits/stdc++.h>
2using namespace std;
3
4int arr[100005] = {};
5int cnt[105] = {};
6int ans[100005] = {};
7
8int main() {
9 int n;
10 cin >> n;
11 for (int i = 0; i < n; ++i) {
12 cin >> arr[i];
13 ++cnt[arr[i]];
14 }
15 for (int i = 2; i <= 100; ++i) {
16 cnt[i] += cnt[i - 1];
17 }
18 for (int i = n - 1; i >= 0; --i) {
19 ans[--cnt[arr[i]]] = arr[i];
20 }
21 for (int i = 0; i < n; ++i) {
22 cout << ans[i] << (i + 1 == n ? "\n" : " ");
23 }
24
25 return 0;
26}计数排序从大到小排序代码
1#include <bits/stdc++.h>
2using namespace std;
3
4int arr[100005] = {};
5int cnt[105] = {};
6int ans[100005] = {};
7
8int main() {
9 int n;
10 cin >> n;
11 for (int i = 0; i < n; ++i) {
12 cin >> arr[i];
13 ++cnt[arr[i]];
14 }
15 for (int i = 99; i >= 1; --i) {
16 cnt[i] += cnt[i + 1];
17 }
18 for (int i = n - 1; i >= 0; --i) {
19 ans[--cnt[arr[i]]] = arr[i];
20 }
21 for (int i = 0; i < n; ++i) {
22 cout << ans[i] << (i + 1 == n ? "\n" : " ");
23 }
24 return 0;
25}总结作业非常重要，请务必认真完成✔️
考试只有一次提交机会，请务必本地检查正确后再提交❇️
请在AC后或者思考15分钟没有进展后查看，不可抄代码❇️
L2054题解+参考代码 题目链接 下载电影：L2054
题解 题目要求我们在给定的 N 小时网速数据中，找到一段连续的 M 小时，其平均网速尽可能大。可以通过前缀和技术高效地计算任意子数组的和。
算法步骤 读取输入：读取两个整数 N 和 M，分别表示总小时数和连续小时数。接着读取 N 个整数，表示每个小时的网速。 计算前缀和数组：创建一个大小为 N+1 的前缀和数组 prefixSum，其中 prefixSum[i] 表示前 i 个小时的网速总和。 计算最大平均网速：遍历所有可能的长度为 M 的子数组，使用前缀和数组快速计算每个子数组的和，并计算其平均值，更新最大平均网速。 输出结果：输出最大平均网速，保留小数点后两位。 示例代码 这里是使用 C++ 实现的示例代码：
1#include <bits/stdc++.h>
2using namespace std;
3
4int main() {
5 // 读取输入
6 int N, M;
7 cin >> N >> M;
8 int speeds[101]; // 最大100个小时
9 for (int i = 1; i <= N; ++i) {
10 cin >> speeds[i];
11 }
12
13 // 计算前缀和数组
14 int prefixSum[101] = {0}; // 前缀和数组，大小为N+1
15 for (int i = 1; i <= N; ++i) {
16 prefixSum[i] = prefixSum[i - 1] + speeds[i];
17 }
18
19 // 计算最大平均网速
20 double maxAverage = -1.0;
21 for (int i = 0; i <= N - M; ++i) {
22 int currentSum = prefixSum[i + M] - prefixSum[i];
23 double currentAverage = double(currentSum) / M;
24 if (currentAverage > maxAverage) {
25 maxAverage = currentAverage;
26 }
27 }
28
29 // 输出结果，保留小数点后两位
30 cout << fixed << setprecision(2) << maxAverage << endl;
31
32 return 0;
33}L2055题解+参考代码 题目链接 品种计数：L2055
题解 题目要求我们对每个查询区间 [a,b]，计算区间内每个品种的奶牛数量。为了高效处理多个查询，可以使用前缀和数组来实现。
算法步骤 读取输入：读取两个整数 N 和 Q，分别表示奶牛数量和查询次数。接着读取 N 个整数，表示每头奶牛的品种编号。然后读取 Q 对整数，表示每个查询的区间 [a,b]。 计算前缀和数组：构建三个前缀和数组，分别记录每个品种奶牛的数量。 处理查询：对于每个查询 [a,b]，利用前缀和数组计算区间内每个品种奶牛的数量。 输出结果：输出每个查询的结果。 示例代码 这里是使用 C++ 实现的示例代码：
1#include <bits/stdc++.h>
2using namespace std;
3const int MAXN = 100005;
4int breed[MAXN];
5int prefix1[MAXN];
6int prefix2[MAXN];
7int prefix3[MAXN];
8
9int main() {
10 // 读取输入
11 int N, Q;
12 cin >> N >> Q;
13 for (int i = 1; i <= N; ++i) {
14 cin >> breed[i];
15 }
16
17 for (int i = 1; i <= N; ++i) {
18 prefix1[i] = prefix1[i - 1] + (breed[i] == 1 ? 1 : 0);
19 prefix2[i] = prefix2[i - 1] + (breed[i] == 2 ? 1 : 0);
20 prefix3[i] = prefix3[i - 1] + (breed[i] == 3 ? 1 : 0);
21 }
22
23 // 处理查询
24 for (int i = 0; i < Q; ++i) {
25 int a, b;
26 cin >> a >> b;
27 int count1 = prefix1[b] - prefix1[a - 1];
28 int count2 = prefix2[b] - prefix2[a - 1];
29 int count3 = prefix3[b] - prefix3[a - 1];
30 cout << count1 << " " << count2 << " " << count3 << endl;
31 }
32
33 return 0;
34}