中 · 前缀和

区间求和

每个区间都现场加一遍，每次都要 O(区间长度)，而问题会一直来。前缀和把所有工作挪到一次预处理：prefix[i] 是前 i 个数的和，于是任何区间都变成一次减法。

一句话答案先用一遍算出 <code>prefix[i] = prefix[i-1] + a[i]</code>（i 从 1 到 n）。区间 [l, r] 的答案就是 <code>prefix[r] - prefix[l-1]</code> —— 每次查询一次减法，总和可达 10^13，要用 <code>long long</code>。

题目

输入: 第一行是 n 和 q（1 ≤ n ≤ 10000，1 ≤ q ≤ 10000）。第二行 n 个整数（−10^9 ≤ a_i ≤ 10^9）。接下来 q 行，每行 l 和 r（1 ≤ l ≤ r ≤ n）。

输出: q 行：每个查询输出 a[l..r] 的和，一行一个。

样例:

输入输出
5 3
1 2 3 4 5
1 5
2 4
3 3		15
9
3

从 1 开始计数的约定在这里悄悄干活：prefix[0] = 0 让公式在 l = 1 时也不用特判。差一错误就住在这条缝里 —— 见下面的错误示例。

你的解答

main.cpp — 你的解答
「运行我的输入」用的自定义输入

判题在浏览器本地运行。死循环会在 3 秒后被自动中断 —— 但还是确保每个循环都有出口。代码随打随存。

卡住了？提示

提示 1 — 让 prefix[i] 把 a[i] 也算进去

把含义定成 prefix[i] = a[1] + … + a[i]，并令 prefix[0] = 0。于是 a[l..r] 的和自动裂项：到 r 为止的全部，减去 l 之前的全部。这题一半的差一错误，都来自两种约定混着用。

提示 2 — 数组从 1 数，而 C++ 从 0 数

把数组开大一格，直接不用第 0 格（或把 0 存进去），让 a[1..n] 和 prefix[1..n] 停在自然下标上。在代码里到处撒 - 1 去和约定搏斗，正是符号错误的诞生方式。

提示 3 — int 装不下这些和

单个元素装得进 int（最多 10^9），但 n 个加起来是 10^13 —— 远超 int 约 2.1 × 10^9 的天花板。把 prefix 声明成 long long。溢出不会崩溃，只会悄悄绕回一个错误的数 —— 这是最阴险的一类 bug。

题解（先自己试试！） 
#include <iostream>
using namespace std;

long long prefix[10005];

int main() {
    int n, q;
    cin >> n >> q;

    prefix[0] = 0;
    for (int i = 1; i <= n; i++) {
        long long x;
        cin >> x;
        prefix[i] = prefix[i - 1] + x;
    }

    for (int k = 0; k < q; k++) {
        int l, r;
        cin >> l >> r;
        cout << prefix[r] - prefix[l - 1] << endl;
    }
    return 0;
}

前缀和是你第一次在知道问题之前就先把结构建好的做法 —— 同一个想法在 最大子段和 里还会回来：用前缀之差一趟扫出最优窗口。当查询之外还要修改，下一个工具是差分数组，再往后是树。

深度解析

为什么这样做对

把「跑动中的总和」存下来。prefix[r] - prefix[l-1] 会抵消两个前缀共有的部分，剩下的恰好是 a[l] + … + a[r]。和筛法、计数排序的桶一样，都是先把结构建好、再用差值回答。

代价

建表 O(n)，每次查询 O(1)，空间 O(n)。暴力是 O(n·q) —— n = q = 10000 时是 1 亿次加法对 2 万次的差别。

常见错法

  • 答成 prefix[r] - prefix[l] —— 悄悄丢掉了 a[l]。公式是 prefix[l-1]，只用 l = 1 的测试会把这个 bug 藏起来。
  • prefix 用 int 存：单个元素装得下，总和装不下。溢出悄悄回绕，答案只是看起来像对的。

下一步

「跑动总和」的技巧在 最大子段和 里以 Kadane 洞察的名义回归 —— 最优窗口就是两个前缀之差。

记住这两句

  • prefix[i] = a[1] + … + a[i]；区间 = prefix[r] − prefix[l−1]。
  • 很多 int 相加要用 long long —— 溢出是悄悄发生的。
🐞 这段是错的 —— 点开,亲手让它挂一次

答的是 prefix[r] - prefix[l] —— 悄悄丢掉了 a[l]

#include <iostream>
using namespace std;

long long prefix[10005];

int main() {
    int n, q;
    cin >> n >> q;
    prefix[0] = 0;
    for (int i = 1; i <= n; i++) {
        long long x;
        cin >> x;
        prefix[i] = prefix[i - 1] + x;
    }
    for (int k = 0; k < q; k++) {
        int l, r;
        cin >> l >> r;
        cout << prefix[r] - prefix[l] << endl;
    }
    return 0;
}