练习6 提示 设置 返回主界面 课程目录 控制室的大门上会显示 n 个数字a[1],a[2]...a[n]，接下来会有m次询问。每次询问会给出一个数字k，需要回答a[1]+a[2]+...+a[k]的和是多少才能打开大门。(1 ≤ n,m ≤ 100000, 1 ≤ a[i] ≤ 1000, 1 ≤ k ≤ n) 输入: 第一行两个数n和m。第二行n个数，为a[1]~a[n]。第三行m个数，依次表示每次询问的k。 输出: m行，每行一个数，为每次询问的答案。 输入样例: 5 3 3 3 4 5 6 2 1 4 输出样例: 6 3 15 技术语言：C++

好的，这是一个非常经典的 **前缀和（Prefix Sum）** 问题。对于频繁的区间求和查询，前缀和是最高效的预处理方法。下面我将用C++为你详细解答。 ## 💡 问题分析 题目要求我们处理 **n个数字** 和 **m次询问**。每次询问给定一个 `k`，需要输出数组前 `k` 个元素的和。 直接每次循环累加前 `k` 个数的复杂度是 **O(n*m)**，在 `n,m` 最大为100,000时，运算量会高达 `10^10`，这是会超时的。 使用 **前缀和** 可以将每次查询的时间复杂度降为 **O(1)**，总复杂度降为 **O(n+m)**，非常高效。 ## 🚀 前缀和核心思想 1. **预处理**：创建一个前缀和数组 `prefix`，其中 `prefix[i]` 表示原数组 `a[1]` 到 `a[i]` 的累积和。 2. **递推公式**：`prefix[i] = prefix[i-1] + a[i]`。通常为了方便，我们会让 `prefix[0] = 0`。 3. **快速查询**：要查询前 `k` 个数的和，直接返回 `prefix[k]` 即可。 ## 🧩 C++ 代码实现 ```cpp #include <iostream> #include <vector> using namespace std; int main() { // 1. 读取 n 和 m int n, m; cin >> n >> m; // 2. 定义原数组和前缀和数组（下标从1开始，方便理解） vector<int> a(n + 1, 0); vector<long long> prefix(n + 1, 0); // 用 long long 防止溢出 // 3. 读取数组 a，并同时计算前缀和 for (int i = 1; i <= n; ++i) { cin >> a[i]; prefix[i] = prefix[i - 1] + a[i]; } // 4. 处理 m 次查询 for (int i = 0; i < m; ++i) { int k; cin >> k; // 直接输出前缀和数组中对应的值 cout << prefix[k] << endl; } return 0; } ``` ### 🔍 代码详细解释 1. **`vector<int> a(n + 1, 0)`**: * 创建一个大小为 `n+1` 的整型向量，下标从 `0` 到 `n`。 * 我们使用 `a[1]` 到 `a[n]` 存储输入数据，`a[0]` 保持为 `0`，这样 `prefix[0]` 就是 `0`，方便后续计算。 2. **`vector<long long> prefix(n + 1, 0)`**: * **重要**：使用 `long long` 类型！ * 题目中 `n` 最大为 100,000，`a[i]` 最大为 1000。在最坏情况下（所有数都是1000），前n个数之和为 `1000 * 100000 = 100,000,000`。这个数虽然 `int` 可以存下，但为了严谨和避免潜在的溢出风险，使用 `long long` 是更好的选择。 3. **`prefix[i] = prefix[i - 1] + a[i]`**: * 这是前缀和的核心递推式，在读取 `a[i]` 的同时计算，一次循环完成输入和预处理，非常高效。 4. **`cout << prefix[k] << endl;`**: * 直接查询 `prefix[k]`，即 `a[1] + a[2] + ... + a[k]`，时间复杂度为 **O(1)**。 ## 🛠️ 环境准备 & 编译运行 ### 环境要求 * 需要安装 **C++ 编译器**，如 `g++` (GCC) 或 `clang++` (LLVM)。 * 对于 Windows，可以使用 MinGW 或 Visual Studio。 * 对于 macOS，可以通过 `xcode-select --install` 安装命令行工具，其中包含 `clang++`。 ### 编译与运行命令 ```bash # 假设你的代码文件名为 main.cpp # 编译 g++ -std=c++11 -O2 -o main main.cpp # 运行，并输入示例数据 ./main # 然后输入: # 5 3 # 3 3 4 5 6 # 2 1 4 ``` * **`-std=c++11`**: 指定使用 C++11 标准，支持 `vector` 等标准库。 * **`-O2`**: 开启优化，提高运行速度。 * **`-o main`**: 指定输出程序文件名为 `main`。 ## 💎 开发建议与最佳实践 1. **优先选择 `long long`**：在处理求和、计数等场景时，即使题目数据看起来在 `int` 范围内，也建议使用 `long long`。这种习惯可以极大避免因数据边界导致的“爆 int”错误，尤其是在在线判题系统中。 2. **活用 `std::vector`**：避免使用 `int a[100005]` 这种固定大小的数组。`std::vector` 可以动态管理内存，代码更现代、更安全。 3. **输入输出优化**： * 如果数据量非常大（例如 n, m > 100,000），C++ 的 `cin` / `cout` 可能会因为需要与 C 的 `stdio` 同步而变慢。可以在 `main` 函数开头添加以下两行代码来加速： ```cpp ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); ``` * 但加上这两行后，就**不能混合使用** `cin` / `cout` 和 `scanf` / `printf` 了。 4. **初始化**：使用 `vector<int> a(n + 1, 0)` 可以确保所有元素被初始化为0，避免未定义行为。 ## 🧪 示例验证 **输入：** ``` 5 3 3 3 4 5 6 2 1 4 ``` **程序运行过程：** * 读取 `n=5, m=3` * 读取 `a[1]=3, a[2]=3, a[3]=4, a[4]=5, a[5]=6` * 计算 `prefix`: * `prefix[0]=0` * `prefix[1]=0+3=3` * `prefix[2]=3+3=6` * `prefix[3]=6+4=10` * `prefix[4]=10+5=15` * `prefix[5]=15+6=21` * 查询1: `k=2` → `prefix[2]=6` * 查询2: `k=1` → `prefix[1]=3` * 查询3: `k=4` → `prefix[4]=15` **输出：** ``` 6 3 15 ``` 完全符合题目要求。这个方法的效率和代码简洁性都非常好！ <br>C++前缀和算法实现：快速求解数组前k项之和<br> ######[AI写代码神器 | 1653点数解答 | 2026-05-22 19:36:58]