题解 | 【模板】静态区间和（前缀和）

题目描述

给定长度为 n 的数组和 q 次查询，每次给出区间 [l, r]，输出该区间元素之和。数组不修改。

初步思路

1. 朴素做法

如果每次查询都直接遍历区间 [l, r] 求和，时间复杂度为 O(n)。对于 q 次查询，总时间复杂度为 O(nq)。

2. 前缀和优化

我们需要快速求出区间和，利用前缀和可以将区间查询优化到 O(1)。

定义：令 pre[i] 表示数组前 i 个元素的和，即：

推导区间和：我们需要求区间 [l, r] 的和：

我们可以用 pre[r] 减去 pre[l-1] 来得到：

• pre[r] 包含了 a[1]...a[r]
• pre[l-1] 包含了 a[1]...a[l-1]
• 相减后，1 到 l-1 部分着消，剩下 l 到 r 部分。

公式：

3. 一个例子

以数组 a = [1, 2, 3, 4, 5] 为例：

• pre[3] = 1 + 2 + 3 = 6
• pre[1] = 1

我们要求区间 [2, 3] 的和，即 a[2] + a[3] = 2 + 3 = 5。

根据公式 sum(2, 3) = pre[3] - pre[1]：

4. 复杂度

• 预处理：O(n)
• 每次查询：O(1)
• 总时间复杂度：O(n + q)

算法分析

• 核心：前缀和转化区间求和
• 技巧：pre[0] = 0，使用 long long 防止溢出
• 时间复杂度：O(n + q)
• 空间复杂度：O(n)

代码实现（C++）

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

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n, q;
    cin >> n >> q;

    vector<long long> pre(n + 1, 0);
    for (int i = 1; i <= n; ++i) {
        long long x;
        cin >> x;
        pre[i] = pre[i - 1] + x;
    }
    while (q--) {
        int l, r;
        cin >> l >> r;
        cout << pre[r] - pre[l - 1] << '\n';
    }
    return 0;
}

总结与反思

1. 静态区间和用前缀和是最直接且高效的模板解法。
2. 注意区间下标从 1 开始时，pre 的边界处理。 特别地，定义 pre[0] = 0。