🧠 C++ 前缀和算法教程（0基础入门）

📚 什么是前缀和？

前缀和（Prefix Sum） 是一种非常实用的算法技巧，用于快速计算一个数组中某个区间内的总和。它的核心思想是：预先处理数组，使得每次查询区间和的时间大大缩短。

---

✅ 学习目标

• 理解前缀和的基本概念
• 掌握如何构建前缀和数组
• 能够使用前缀和解决简单的区间求和问题
• 用 using namespace std; 编写代码，简洁易读

---

🧩 前缀和的应用场景

比如你有一个数组：

int arr[] = {1, 3, 5, 7, 9};

你想知道从第2个元素到第4个元素的和（即 arr[1] + arr[2] + arr[3]），也就是 3+5+7=15。

如果每次都这样加起来，效率很低。
而前缀和可以让你在 O(1) 时间内完成这个操作！

---

🔢 前缀和数组是怎么来的？

我们先构建一个前缀和数组 prefix，其中：

prefix[i] 表示原数组从第0个元素到第i-1个元素的和。

例如：

i	prefix[i]
0	0（默认值）
1	arr[0]
2	arr[0]+arr[1]
3	arr[0]+arr[1]+arr[2]
...

所以对于数组 {1, 3, 5, 7, 9}，前缀和数组是：

prefix[0] = 0
prefix[1] = 1
prefix[2] = 1+3 = 4
prefix[3] = 1+3+5 = 9
prefix[4] = 1+3+5+7 = 16
prefix[5] = 1+3+5+7+9 = 25

---

🛠️ 如何构造前缀和数组？

我们用一个循环来构造它：

#include <iostream>
#include <vector>
using namespace std;

int main() {
    vector<int> arr = {1, 3, 5, 7, 9}; // 原始数组
    int n = arr.size();
    
    // 构建前缀和数组
    vector<int> prefix(n + 1, 0); // 初始全为0
    
    for (int i = 1; i <= n; ++i) {
        prefix[i] = prefix[i - 1] + arr[i - 1];
    }

    // 输出结果
    cout << "前缀和数组为：" << endl;
    for (int i = 0; i <= n; ++i) {
        cout << prefix[i] << " ";
    }
    cout << endl;

    return 0;
}

💡 输出：

前缀和数组为：
0 1 4 9 16 25 

---

🧮 如何快速求某段区间的和？

假设我们要计算从下标 l 到 r 的和（包括 arr[r]），那么：

sum(arr[l] ~ arr[r]) = prefix[r + 1] - prefix[l]

✅ 示例：

想要求 arr[1] + arr[2] + arr[3]（即索引1~3）

• l = 1, r = 3
• sum = prefix[4] - prefix[1] = 16 - 1 = 15

---

📌 实战小练习：LeetCode 风格题目

🧪 题目描述：

给定一个整数数组 nums 和多个查询，每个查询给出一个区间 [left, right]，返回该区间所有元素的和。

你可以多次查询，每次都要快速返回结果。

---

✅ 解题思路：

1. 先构建前缀和数组。
2. 每次查询只需要用公式：sum = prefix[right + 1] - prefix[left]

---

💻 完整代码如下：

#include <iostream>
#include <vector>
using namespace std;

int main() {
    // 原始数组
    vector<int> nums = {1, 3, 5, 7, 9};
    int n = nums.size();

    // 构建前缀和数组
    vector<int> prefix(n + 1, 0);
    for (int i = 1; i <= n; ++i) {
        prefix[i] = prefix[i - 1] + nums[i - 1];
    }

    // 模拟几个查询
    vector<pair<int, int>> queries = {{0, 0}, {1, 3}, {0, 4}, {2, 2}};

    for (auto q : queries) {
        int left = q.first;
        int right = q.second;
        int sum = prefix[right + 1] - prefix[left];

        cout << "区间 [" << left << ", " << right << "] 的和为: " << sum << endl;
    }

    return 0;
}

💡 输出结果：

区间 [0, 0] 的和为: 1
区间 [1, 3] 的和为: 15
区间 [0, 4] 的和为: 25
区间 [2, 2] 的和为: 5

---

🧠 小结：前缀和三步走

1. 初始化前缀和数组（长度比原数组多1）
2. 预处理填充前缀和数组
3. 根据左右边界快速求和

---

🎯 常见应用场景

• 快速求一维数组区间和
• 图像处理中的二维前缀和（图像积分图）
• 数据统计、滑动窗口优化等

---

📝 总结

内容	说明
前缀和定义	用来快速求区间和的预处理数组
时间复杂度	预处理 O(n)，每次查询 O(1)
关键公式	sum(l, r) = prefix[r+1] - prefix[l]
是否适合新手	✅ 非常适合！逻辑清晰，容易实现

---

📚 下一步建议

• 学习二维前缀和（矩阵区域和）
• 尝试用前缀和解决 LeetCode 简单题如：
  • 303. 区域和检索 - 数组不可变
  • 560. 和为 K 的子数组（进阶）

✅ C++ 前缀和教程

一、什么是前缀和？

在编程中，我们经常需要计算一个数组中某个区间的总和。比如：

arr = [1, 3, 5, 7, 9]

你想知道从第2个元素到第4个元素的和：3 + 5 + 7 = 15。

如果你每次都要重新加一遍，效率会很低，尤其是在数据量大的时候。

前缀和（Prefix Sum） 就是为了解决这个问题的一种技巧 —— 它通过预处理的方式，让我们可以在 O(1) 时间内快速查出任意区间和！

---

二、前缀和数组是怎么来的？

前缀和数组 prefix 的构造方式如下：

• prefix[0] = arr[0]
• prefix[1] = prefix[0] + arr[1]
• prefix[2] = prefix[1] + arr[2]
• ...
• prefix[i] = prefix[i - 1] + arr[i]

这样构造出来的数组就叫 前缀和数组。

📌 示例

原数组：

arr = [1, 3, 5, 7, 9]

对应的前缀和数组：

prefix = [1, 4, 9, 16, 25]

---

三、C++ 实现：如何构造前缀和数组？

#include <iostream>
#include <vector>
using namespace std; // 使用标准命名空间，避免重复写std::

这是本教程中非常关键的一行代码，它允许我们在后续代码中省略 std:: 前缀，使代码更简洁。

下面是完整的构建代码：

int main() {
    vector<int> arr = {1, 3, 5, 7, 9}; // 原始数组
    int n = arr.size();

    // 创建前缀和数组，大小与原数组相同
    vector<int> prefix(n);

    // 构建前缀和数组
    prefix[0] = arr[0]; // 第一个元素直接赋值
    for (int i = 1; i < n; i++) {
        prefix[i] = prefix[i - 1] + arr[i];
    }

    // 输出结果
    cout << "原数组: ";
    for (int num : arr) {
        cout << num << " ";
    }
    cout << "\n前缀和数组: ";
    for (int num : prefix) {
        cout << num << " ";
    }
    cout << endl;

    return 0;
}

💡 输出结果：

原数组: 1 3 5 7 9 
前缀和数组: 1 4 9 16 25 

---

四、使用前缀和求任意区间和

前缀和最大的用处就是快速查询任意区间的和。

公式如下：

sum[l...r] = prefix[r] - (l == 0 ? 0 : prefix[l - 1]);

✅ 示例：

我们要查 arr[1] 到 arr[3] 的和（即 3 + 5 + 7 = 15）：

prefix[3] = 16  
prefix[0] = 1   （因为 l=1，所以 l-1=0）
sum = 16 - 1 = 15

---

五、封装成函数：方便调用

我们可以把这个逻辑封装成一个函数，让代码更清晰、复用性更高。

// 查询区间 [l, r] 的和
int rangeSum(const vector<int>& prefix, int l, int r) {
    if (l == 0) {
        return prefix[r]; // 如果起点是0，直接返回prefix[r]
    } else {
        return prefix[r] - prefix[l - 1]; // 否则用差值
    }
}

然后在主函数中调用它：

int l = 1, r = 3;
int sum = rangeSum(prefix, l, r);
cout << "arr[" << l << "]到arr[" << r << "]的和是：" << sum << endl;

🧾 输出结果：

arr[1]到arr[3]的和是：15

---

六、前缀和的优势总结

特点	说明
⏱ 预处理时间复杂度	O(n)，只需一次遍历即可构建
🔍 查询时间复杂度	O(1)，无论区间多大都只做一次减法
🧠 空间复杂度	O(n)，需要额外存储一个数组

非常适合用于频繁查询区间和的场景！

---

七、注意事项

1. 数组不能为空，否则前缀和无法构造。
2. 数组不能频繁修改，一旦原数组变化，必须重新构造前缀和数组。
3. 适合静态数组，如果数据经常变动，可以考虑其他技巧如线段树或差分数组。

---

八、小练习：子数组最大和

题目：给定一个整数数组，找出具有最大和的连续子数组（至少包含一个元素），返回其最大和。

虽然这不是传统前缀和题，但可以用它来解！

思路简述：

• 记录当前最小的前缀和
• 每次比较当前前缀和与最小前缀和的差值，取最大即可

#include <climits>

int maxSubArray(vector<int>& nums) {
    int n = nums.size();
    vector<int> prefix(n);
    
    prefix[0] = nums[0];
    for (int i = 1; i < n; ++i) {
        prefix[i] = prefix[i - 1] + nums[i];
    }

    int minPrefix = 0;
    int maxSum = INT_MIN;

    for (int i = 0; i < n; ++i) {
        maxSum = max(maxSum, prefix[i] - minPrefix);
        minPrefix = min(minPrefix, prefix[i]);
    }

    return maxSum;
}

---

九、总结回顾

步骤	内容
1️⃣	构造前缀和数组
2️⃣	使用 prefix[r] - prefix[l - 1] 快速求区间和
3️⃣	可以封装成函数提高代码可读性
4️⃣	注意数组不能频繁修改

---

十、扩展学习建议

如果你想继续深入学习以下内容，欢迎继续提问，我可以为你准备进阶教程：

• ✅ 二维前缀和（矩阵区域求和）
• ✅ 差分数组（区间增减操作）
• ✅ 滑动窗口（连续子数组问题）
• ✅ 前缀和 + 哈希表（子数组和为k的问题）

---

📌 关键词复习：

• 前缀和数组
• 区间和查询
• O(1) 查询
• 静态数组优化
• 数组预处理

C++ 前缀和教程（通俗易懂，0基础）

一、什么是前缀和？

前缀和（Prefix Sum） 是一种非常实用的技巧，用于快速求出数组中某个区间的所有元素之和。

简单来说：

假设你有一个数组 arr = [a1, a2, a3, ..., an]，你想知道从第 l 个元素到第 r 个元素的总和（即 arr[l] + arr[l+1] + ... + arr[r]），如果你每次都重新加一遍，效率会很低。

前缀和就是为了解决这个问题：

我们先预处理一个“前缀和数组” prefix，其中：

prefix[0] = 0
prefix[1] = arr[0]
prefix[2] = arr[0] + arr[1]
prefix[3] = arr[0] + arr[1] + arr[2]
...
prefix[i] = arr[0] + arr[1] + ... + arr[i-1]

这样，当你想计算 arr[l] 到 arr[r] 的和时，只需要：

sum = prefix[r + 1] - prefix[l]

---

二、举个例子

我们来看一个例子：

原始数组：

arr = [2, 1, 3, 6, 4]

对应的前缀和数组是：

prefix[0] = 0
prefix[1] = 2
prefix[2] = 2 + 1 = 3
prefix[3] = 3 + 3 = 6
prefix[4] = 6 + 6 = 12
prefix[5] = 12 + 4 = 16

所以 prefix = [0, 2, 3, 6, 12, 16]

如果我们想知道 arr[1] 到 arr[3] 的和（也就是 1 + 3 + 6 = 10），可以这样做：

sum = prefix[4] - prefix[1] = 12 - 2 = 10

是不是很快？

---

三、如何构建前缀和数组？

我们可以用一个简单的循环来构造前缀和数组。

#include <iostream>
#include <vector>
using namespace std;

int main() {
    vector<int> arr = {2, 1, 3, 6, 4};  // 原始数组
    int n = arr.size();

    // 创建前缀和数组，长度比原数组多1
    vector<int> prefix(n + 1, 0);

    // 构建前缀和数组
    for (int i = 1; i <= n; i++) {
        prefix[i] = prefix[i - 1] + arr[i - 1];
    }

    // 输出前缀和数组
    cout << "前缀和数组为：" << endl;
    for (int i = 0; i <= n; i++) {
        cout << prefix[i] << " ";
    }
    cout << endl;

    return 0;
}

输出结果：

前缀和数组为：
0 2 3 6 12 16 

---

四、如何使用前缀和求区间和？

我们再写一个函数，用来快速查询任意区间的和。

#include <iostream>
#include <vector>
using namespace std;

// 求区间 [l, r] 的和（下标从0开始）
int querySum(const vector<int>& prefix, int l, int r) {
    return prefix[r + 1] - prefix[l];
}

int main() {
    vector<int> arr = {2, 1, 3, 6, 4};
    int n = arr.size();
    vector<int> prefix(n + 1, 0);

    for (int i = 1; i <= n; i++) {
        prefix[i] = prefix[i - 1] + arr[i - 1];
    }

    // 查询 arr[1] 到 arr[3] 的和
    int l = 1, r = 3;
    int sum = querySum(prefix, l, r);
    cout << "arr[" << l << "]到arr[" << r << "]的和是：" << sum << endl;

    return 0;
}

输出结果：

arr[1]到arr[3]的和是：10

---

五、前缀和的优点

特点	说明
✅ 预处理时间复杂度 O(n)	只需要一次遍历就能建立前缀和数组
✅ 查询区间和时间复杂度 O(1)	每次查询只需一次减法操作
✅ 空间复杂度 O(n)	多开一个数组

---

六、小练习：连续子数组的最大和

题目：给定一个整数数组 nums，找到一个具有最大和的连续子数组（子数组长度至少为1），返回它的最大和。

虽然这不是典型的前缀和题，但我们也可以用它来做！

思路：记录当前最小的前缀和，然后每次比较当前前缀和与最小前缀和的差值，取最大即可。

#include <iostream>
#include <vector>
#include <climits>
using namespace std;

int maxSubArray(vector<int>& nums) {
    int n = nums.size();
    vector<int> prefix(n + 1, 0);
    
    for (int i = 1; i <= n; i++) {
        prefix[i] = prefix[i - 1] + nums[i - 1];
    }

    int minPrefix = 0;
    int maxSum = INT_MIN;

    for (int i = 1; i <= n; i++) {
        maxSum = max(maxSum, prefix[i] - minPrefix);
        minPrefix = min(minPrefix, prefix[i]);
    }

    return maxSum;
}

int main() {
    vector<int> nums = {-2, 1, -3, 4, -1, 2, 1, -5, 4};
    cout << "最大子数组和为：" << maxSubArray(nums) << endl;
    return 0;
}

输出结果：

最大子数组和为：6

---

七、总结

步骤	内容
1️⃣	定义一个比原数组长1的前缀和数组 prefix
2️⃣	使用循环填充 prefix[i] = prefix[i-1] + arr[i-1]
3️⃣	查询区间 [l, r] 的和：prefix[r+1] - prefix[l]

---

八、常见问题

Q1：为什么前缀和数组要比原数组长1？

A：为了方便处理边界情况（比如从第一个元素开始的区间），让 prefix[0] = 0，这样公式统一。

Q2：可以用在二维数组吗？

A：当然可以！这叫 二维前缀和，适合处理矩阵区域求和的问题。这个会在进阶篇讲解。

---

如果你想继续学习 二维前缀和、差分数组、滑动窗口等 技巧，欢迎告诉我，我可以为你准备下一讲内容 😊

---

📌 关键词复习：

• 前缀和数组
• 区间求和
• prefix[r+1] - prefix[l]
• 时间复杂度优化
• 数组预处理