[OI 基础训练] 静态数组区间求和 (前缀和模板)

一、 题目背景与知识点讲解

在信息学竞赛中，我们经常遇到需要对一个数组进行多次查询的情况。

场景描述： 假设你有一个数组 nums，它的内容是固定不变的（即“Immutable”）。现在有大量的查询请求，每个请求都会给出一个区间 [left, right]，要求你计算这个区间内所有元素的和。

1. 暴力解法 (Naive Approach) 最直观的方法是对于每一次查询，都写一个 for 循环从 left 遍历到 right 进行累加。

• 时间复杂度：如果是 $M$ 次查询，数组长度为 $N$，每次查询最坏情况是 $O(N)$。总时间复杂度为 $O(M \times N)$。
• 后果：当 $N$ 和 $M$ 都达到 $10^5$ 级别时，运算量会达到 $10^{10}$，导致程序超时 (Time Limit Exceeded)。

2. 优化解法：前缀和 (Prefix Sum) 既然数组不会变，我们可以运用**“预处理”**的思想，用空间换时间。 我们定义一个辅助数组 preSum，其中 preSum[i] 表示原数组前 i 个元素的总和。

• 定义：

  • 设原数组为 $A$（为了方便计算，通常下标从 1 开始）。
  • $preSum[i] = A[1] + A[2] + \dots + A[i]$。
  • 特别地，定义 $preSum[0] = 0$。

• 递推公式：

  $$preSum[i] = preSum[i-1] + A[i]$$

• 区间求和公式： 如果要求区间 $[L, R]$ 的和（即 $A[L] + \dots + A[R]$），我们可以利用前缀和数组快速计算：

  $$Sum(L, R) = preSum[R] - preSum[L-1]$$
  • 解释：前 $R$ 个数的和，减去前 $L-1$ 个数的和，剩下的就是第 $L$ 到第 $R$ 个数的和。

• 复杂度分析：

  • 预处理时间：遍历一次数组，复杂度 $O(N)$。
  • 查询时间：利用公式直接计算，复杂度 $O(1)$。
  • 总时间复杂度：$O(N + M)$。这是一个巨大的提升。

二、 题目描述

给定一个包含 $N$ 个整数的数组 $A$。该数组在后续过程中不会发生改变。 接下来会有 $M$ 次查询，每次查询给定两个整数 $L$ 和 $R$，请你计算并输出数组中从下标 $L$ 到下标 $R$（包含 $L$ 和 $R$）的所有元素之和。

为了方便处理边界情况，本题约定数组下标从 $1$ 开始计数。

输入格式

第一行包含两个整数 $N$ 和 $M$，分别表示数组元素的个数和查询的次数。 第二行包含 $N$ 个整数 $A_1, A_2, \dots, A_N$，表示数组的元素。 接下来 $M$ 行，每行包含两个整数 $L$ 和 $R$，表示查询的区间范围。

输出格式

对于每一次查询，输出一行一个整数，表示该区间的和。

数据范围

• $1 \le N, M \le 10^5$
• $-1000 \le A_i \le 1000$
• $1 \le L \le R \le N$
• 结果保证在 32 位有符号整数范围内（但在竞赛中建议使用 long long 以防万一）。

样例输入

6 3
-2 0 3 -5 2 -1
1 3
3 6
1 6

样例输出

1
-1
-3

样例解释

• 数组为 [-2, 0, 3, -5, 2, -1] (1-based)。
• 查询 [1, 3]：$(-2) + 0 + 3 = 1$。
• 查询 [3, 6]：$3 + (-5) + 2 + (-1) = -1$。
• 查询 [1, 6]：所有元素之和为 -3。

三、 标准代码 (C++14 OI风格)

/**
 * 题目：静态数组区间求和
 * 知识点：前缀和 (Prefix Sum)
 * 时间复杂度：预处理 O(N), 查询 O(1), 总计 O(N+M)
 * 空间复杂度：O(N)
 */

#include <iostream>
#include <vector>

using namespace std;

// 定义长整型，防止累加过程中溢出（虽然本题数据范围int够用，但养成好习惯）
typedef long long ll;

const int MAXN = 100005; 
// 在全局定义数组，防止栈溢出，且自动初始化为0
// preSum[i] 存储 A[1]...A[i] 的和
ll preSum[MAXN]; 

int main() {
    // 1. IO 读写优化，竞赛必备，加快 cin/cout 速度
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n, m;
    if (!(cin >> n >> m)) return 0;

    // 2. 读入数据并预处理前缀和
    // 技巧：我们不需要存储原数组 nums，直接边读边计算 preSum 即可节省空间
    // preSum[0] 默认为 0，符合逻辑
    for (int i = 1; i <= n; ++i) {
        int x;
        cin >> x;
        // 核心递推公式：当前前缀和 = 上一个前缀和 + 当前数值
        preSum[i] = preSum[i - 1] + x;
    }

    // 3. 处理 M 次查询
    for (int k = 0; k < m; ++k) {
        int l, r;
        cin >> l >> r;
        
        // 4. O(1) 输出结果
        // 核心查询公式：Sum(L, R) = preSum[R] - preSum[L-1]
        cout << preSum[r] - preSum[l - 1] << "\n";
    }

    return 0;
}

四、 教学备课重点 (教练参考)

1. 下标处理：
   • LeetCode303 原题是 0-indexed（下标从0开始），公式是 sumRange(i, j) = preSum[j+1] - preSum[i]。
   • 在 OI 中，为了避免处理 L-1 变成 -1 的越界情况，通常建议让数组下标从 1 开始。这样 preSum[0] 天然就是 0，代码逻辑更统一（即 preSum[R] - preSum[L-1]）。
2. 不可变性 (Immutable)：
   • 向学生强调，这种 $O(1)$ 查询的前提是数组不修改。如果数组元素频繁修改，前缀和数组就需要重新计算（$O(N)$），此时需要更高级的数据结构（如树状数组或线段树）。
3. 空间换时间：
   • 讲解前缀和的本质是缓存。我们把计算过的结果存起来，下次直接用减法还原。这是算法设计中非常核心的思想。
4. 溢出风险：
   • 虽然单个元素很小，但 $10^5$ 个元素累加可能会超过 int 范围。虽然本题数据范围限制了总和在 int 内，但建议学生在涉及“求和”类题目时优先考虑 long long。