学会前缀和，区间求和不再慢——给C++小勇士的实用技巧

小朋友，你有没有遇到过这样的问题：老师给了你一串数字，比如每天的零花钱，然后问你“从第2天到第5天一共花了多少钱”？如果每次都从头加一遍，数字多了会很慢。今天我们来认识一个神奇的工具——前缀和，它能帮我们瞬间算出任意一段数字的总和。

什么是前缀和？——像记“累计账本”一样简单

想象你有一排糖果盒子，每个盒子里放着不同数量的糖果。你想知道从第一个盒子到第三个盒子一共有多少颗糖？你可以一个一个数，但如果有100个盒子，每次都要从头数就很麻烦。

前缀和的做法是：先准备一个新的盒子列表，在每个位置都记下“从第一个盒子到这里的所有糖果总数”。比如：

位置1：盒子1的糖果数
位置2：盒子1+盒子2的糖果数
位置3：盒子1+盒子2+盒子3的糖果数
……

这样，如果你想算第 i 个盒子到第 j 个盒子的糖果总数，只需要用“位置 j 的总数”减去“位置 i-1 的总数”就行了！因为“前 j 个的总数”减去“前 i-1 个的总数”正好就是第 i 到 j 的糖果数。

生活里还有更多例子：

零花钱：小明每天存零花钱，存入金额记录在数组里。妈妈想知道从第3天到第7天一共存了多少。用前缀和，1秒就算出来。
考试成绩：全班同学的成绩排成一排，老师想快速知道某一段同学的总分，用前缀和，一次减法搞定。
排队领零食：每个同学领到的零食数量不同，班长想知道从第5个同学到第10个同学一共多少零食，也是前缀和的拿手好戏。

前缀和的核心公式——记住“累加”和“相减”

前缀和的数学表达很简单：
设原数组为 a[1], a[2], ..., a[n]（注意，我们通常从下标1开始存，这样计算更方便）。
定义一个前缀和数组 prefix，其中 prefix[i] 表示 a[1] 到 a[i] 的总和。
计算公式：

prefix[i] = prefix[i-1] + a[i]    （i ≥ 1，且 prefix[0] = 0）

如果要计算原数组中区间 [L, R] 的和（即从第L个到第R个），只需要：

区间和 = prefix[R] - prefix[L-1]

因为 prefix[R] 包含了前R个， prefix[L-1] 包含了前L-1个，一减就得到中间那段。
口诀：“右减左减一”。

怎么用C++写前缀和？——动手写代码

我们用一个数组 a 存储原始数字，再用一个数组 prefix 存储前缀和。核心代码很简单：

#include <iostream>
using namespace std;

int main() {
    int a[100], prefix[100]; // a存原始数据，prefix存前缀和
    int n;                    // 数字个数
    cout << "请输入数字个数：";
    cin >> n;

    // 从下标1开始读入原始数据（方便计算）
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
    }

    // 计算前缀和，prefix[0]设为0
    prefix[0] = 0; // 第0个位置设为0，方便计算
    for (int i = 1; i <= n; i++) {
        prefix[i] = prefix[i-1] + a[i];
    }

    // 比如求第2个到第5个的和
    int left = 2, right = 5;  // 左边界和右边界
    int sum = prefix[right] - prefix[left-1];
    cout << "第" << left << "个到第" << right << "个的和是：" << sum << endl;

    return 0;
}

你看，只要提前算好前缀和，后面的任何区间求和都只需要一次减法，非常快。

常见错误——初学者容易踩的坑

忘记初始化 prefix[0] = 0
如果 prefix[0] 没有赋值，默认是一个随机值，减法就会出错。一定要先设成0。
数组下标从0开始，但公式里用了从1开始
如果原数组下标从0开始（比如 a[0], a[1]...），那么计算区间 [L, R] 的和时，公式要改成 prefix[R] - prefix[L-1]，但 prefix[0] 仍然代表前0个的和，即0。为了避免混淆，最稳妥的方法是让数组下标从1开始存储数据，把 a[0] 或 prefix[0] 空出来当作哨兵。
数组越界
计算 prefix[i] 时，i 最大是n，所以 prefix 数组至少要有 n+1 个元素（下标0到n）。如果只开了 n 个，就会越界。
多次查询时，每次重新计算前缀和
既然前缀和只需要一次预处理，就把它放在程序开头。不要每次查询都重新算一遍，那样就白费功夫了。

完整示例——让程序自己回答多个区间问题

下面是一个完整的程序，用户可以多次输入左右边界，程序立即输出区间和，直到用户输入“0 0”结束。

#include <iostream>
using namespace std;

int main() {
    int a[100], prefix[100]; // a存原始数据，prefix存前缀和
    int n;                    // 数字个数

    cout << "请输入数字个数：";
    cin >> n;

    // 读入n个数字，从下标1开始存
    cout << "请输入" << n << "个数字：";
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
    }

    // 计算前缀和
    prefix[0] = 0; // 前0个数的和为0
    for (int i = 1; i <= n; i++) {
        prefix[i] = prefix[i-1] + a[i];
    }

    // 开始多次查询
    cout << "请输入要查询的区间左右边界（左 右），输入0 0结束：\n";
    int left, right; // 左边界，右边界
    while (true) {
        cin >> left >> right;
        if (left == 0 && right == 0) break; // 结束条件
        if (left < 1 || right > n || left > right) {
            cout << "输入不合法，请重新输入：\n";
            continue;
        }
        int sum = prefix[right] - prefix[left-1];
        cout << "第" << left << "个到第" << right << "个的和是：" << sum << endl;
    }

    return 0;
}

运行示例：

请输入数字个数：5
请输入5个数字：3 8 2 5 1
请输入要查询的区间左右边界（左 右），输入0 0结束：
2 4
第2个到第4个的和是：15
1 5
第1个到第5个的和是：19
0 0

小总结

前缀和就是把累加结果提前存起来，使用时直接相减。它特别适合需要多次求连续区间和的问题，比如统计考试分数的总分段。记住：prefix[i] = prefix[i-1] + a[i]，区间 [l, r] 的和等于 prefix[r] - prefix[l-1]。

什么是前缀和？——快速算出累加结果的小助手