一维前缀和
一、课上练习
编程练习
二、知识总结
✨ 一维前缀和的核心思想
假设有一个数组，你需要多次查询不同区间的元素之和。每次都从头加到尾的话，查询一次就需要 O(n) 的时间，查询 m 次就是 O(n×m)，当数据量大时效率很低。
一维前缀和（Prefix Sum）就是用来解决这个问题的——通过一次 O(n) 的预处理，之后每次区间和查询都只需要 O(1) 的时间。
✨ 一维前缀和的计算方法
假设有一个数组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] + array[i];
}✨ 一维前缀和的复杂度分析
复杂度：
- 时间复杂度：O(n)（预处理），O(1)（单次区间查询）
- 空间复杂度：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);
}✨ 一维前缀和的执行示例
问题：给定数组 array = {0, 3, 1, 4, 1, 5}（下标从1开始，array[0]不使用），求第2个到第4个元素的区间和。
第一步：构建前缀和数组
| i | array[i] | 计算过程 | prefix[i] |
|---|---|---|---|
| 0 | - | 初始值 | 0 |
| 1 | 3 | prefix[0] + array[1] = 0 + 3 | 3 |
| 2 | 1 | prefix[1] + array[2] = 3 + 1 | 4 |
| 3 | 4 | prefix[2] + array[3] = 4 + 4 | 8 |
| 4 | 1 | prefix[3] + array[4] = 8 + 1 | 9 |
| 5 | 5 | prefix[4] + array[5] = 9 + 5 | 14 |
第二步：查询区间 [2, 4] 的和
区间和 = prefix[4] - prefix[2-1] = prefix[4] - prefix[1] = 9 - 3 = 6
验证： array[2] + array[3] + array[4] = 1 + 4 + 1 = 6 ✓
关键理解： prefix[r] 存储的是前r个元素的总和，减去 prefix[l-1]（前l-1个元素的总和），剩下的就恰好是第l个到第r个元素的和。
✨ 解题步骤详解：最大子段和
问题：给定数组，找到一段连续子数组，使其元素之和最大。
思考过程：
第一步：暴力思路。 枚举所有区间 [l, r]，计算每个区间的和，取最大值。时间复杂度 O(n²) 或 O(n³)。
第二步：前缀和优化。 任意区间和 = prefix[r] - prefix[l-1]。要让区间和最大，就是要让 prefix[r] - prefix[l-1] 最大。
第三步：关键观察。 对于固定的右端点 r，prefix[r] 是固定的，要让差最大，只需让 prefix[l-1] 最小。所以我们在遍历过程中维护一个"到目前为止的最小前缀和"即可。
第四步：执行演示。 以 array = {2, -3, 1, 4, -1} 为例：
| i | array[i] | prefix[i] | min_prefix | prefix[i]-min_prefix | maxsubsum |
|---|---|---|---|---|---|
| 1 | 2 | 2 | 0 | 2-0=2 | 2 |
| 2 | -3 | -1 | 0 | -1-0=-1 | 2 |
| 3 | 1 | 0 | -1 | 0-(-1)=1 | 2 |
| 4 | 4 | 4 | -1 | 4-(-1)=5 | 5 |
| 5 | -1 | 3 | -1 | 3-(-1)=4 | 5 |
最终结果：最大子段和为 5，对应子段 [1, 4]（区间 [3,4]），即 prefix[4] - prefix[2] = 4 - (-1) = 5。
✨ 一维前缀和的常见错误
- 下标偏移错误：区间和公式是
prefix[r] - prefix[l-1]，注意减的是 l-1 而不是 l。如果写成prefix[r] - prefix[l]，就会少算一个元素。 - prefix[0] 忘记初始化为0：prefix[0] = 0 是前缀和的基础，如果忘记设置，查询包含第一个元素的区间时会出错。
- 数组下标从0还是从1开始搞混：前缀和通常让数组下标从1开始更方便（prefix[0]=0 作为哨兵），如果从0开始需要额外处理边界。
- 数据溢出：前缀和可能很大。如果原数组有 10^5 个元素，每个元素最大 10^9，前缀和最大可达 10^14，需要使用 long long 类型。
✨ 前缀和在计数排序中的应用（进阶内容）
以下内容需要学习过计数排序后再来阅读。
计数排序的核心问题是：知道每个数出现了几次，如何确定每个数在排序结果中的位置？ 这正是前缀和可以解决的。
原理：
- 先统计每个数值出现的次数，存入计数数组
cnt - 对
cnt做前缀和，此时cnt[v]的含义变为"值 ≤ v 的元素一共有多少个"，也就是值为 v 的元素在排序结果中的最后位置 - 从后往前遍历原数组，将每个元素放到
cnt指示的位置上，放完后cnt减 1
示例： 对数组 {3, 1, 2, 1, 3} 从小到大排序
| 步骤 | 说明 |
|---|---|
| 统计次数 | cnt = {0, 2, 1, 2}（1出现2次，2出现1次，3出现2次） |
| 前缀和 | cnt = {0, 2, 3, 5}（≤1有2个，≤2有3个，≤3有5个） |
| 放置元素 | 从后往前：arr[4]=3 → ans[4], arr[3]=1 → ans[1], arr[2]=2 → ans[2], arr[1]=1 → ans[0], arr[0]=3 → ans[3] |
| 排序结果 | ans = {1, 1, 2, 3, 3} |
如果要从大到小排序，只需将前缀和改为后缀和（从右往左累加），此时 cnt[v] 表示"值 ≥ v 的元素一共有多少个"。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}