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

题目链接

题目描述

对于给定的长度为 $n$ 的数组 $a$ ，你需要构建一个能够维护区间和信息的数据结构，使得其能支持多次区间和查询。

区间和查询：输出区间 $[l, r]$ 中的元素之和，即 $\sum_{i=l}^{r} a_i$ 。

解题思路

本题是静态区间求和的经典问题，即数组内容不会发生改变。如果每次查询都通过循环遍历从 $l$ 到 $r$ 的元素并求和，当查询次数 $m$ 很大时，总时间复杂度会达到 $O(n \cdot m)$ ，这在 $n$ 和 $m$ 都很大时是无法接受的。

解决这个问题的标准方法是使用前缀和（Prefix Sum）数组。

1. 构建前缀和数组

我们创建一个新的数组，称之为前缀和数组，记为 $S$ 。 $S_i$ 的值定义为原始数组 $a$ 从第一个元素到第 $i$ 个元素的累计总和。

为了计算方便，我们通常让前缀和数组的长度比原数组多一个，并令 $S_0 = 0$ 。然后， $S_i$ 表示原数组前 $i$ 个元素的和（即 $a_1, a_2, \dots, a_i$ 的和）。

前缀和数组的递推公式为： $S_i = S_{i-1} + a_i$ (其中 $i$ 从 $1$ 到 $n$ )

或者说， $S_i = \sum_{k=1}^{i} a_k$

这个构建过程只需要一次遍历，时间复杂度为 $O(n)$ 。

2. 区间和查询

利用构建好的前缀和数组，我们可以用 $O(1)$ 的时间计算出任意区间 $[l, r]$ 的和。

区间 $[l, r]$ 的和等于 (前 $r$ 个元素的和) - (前 $l-1$ 个元素的和)。用公式表示就是： $\text{sum}(l, r) = \sum_{i=l}^{r} a_i = (\sum_{i=1}^{r} a_i) - (\sum_{i=1}^{l-1} a_i) = S_r - S_{l-1}$

这样，我们通过 $O(n)$ 的预处理，将每次查询的复杂度从 $O(n)$ 降到了 $O(1)$ 。

代码

c++
java
python

#include <iostream>
#include <vector>
#include <numeric>

using namespace std;
using LL = long long;

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

    // 前缀和数组，大小为 n+1，索引从1开始
    vector<LL> prefix_sum(n + 1, 0);
    for (int i = 1; i <= n; ++i) {
        LL current_val;
        cin >> current_val;
        prefix_sum[i] = prefix_sum[i - 1] + current_val;
    }

    for (int k = 0; k < m; ++k) {
        int l, r;
        cin >> l >> r;
        // 计算区间和 S[r] - S[l-1]
        cout << prefix_sum[r] - prefix_sum[l - 1] << endl;
    }

    return 0;
}

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int m = sc.nextInt();

        // 前缀和数组，大小为 n+1，索引从1开始
        long[] prefixSum = new long[n + 1];
        prefixSum[0] = 0;
        for (int i = 1; i <= n; i++) {
            prefixSum[i] = prefixSum[i - 1] + sc.nextLong();
        }

        for (int k = 0; k < m; k++) {
            int l = sc.nextInt();
            int r = sc.nextInt();
            // 计算区间和 S[r] - S[l-1]
            System.out.println(prefixSum[r] - prefixSum[l - 1]);
        }
    }
}

# 读取n和m
n, m = map(int, input().split())
# 读取原始数组
a = list(map(int, input().split()))

# 构建前缀和数组
# prefix_sum[i] 存储 a[0]...a[i-1] 的和
prefix_sum = [0] * (n + 1)
for i in range(n):
    prefix_sum[i+1] = prefix_sum[i] + a[i]

# 处理m次查询
for _ in range(m):
    l, r = map(int, input().split())
    # 原始数组的 [l, r] 区间 (1-based)
    # 对应前缀和数组的 prefix_sum[r] - prefix_sum[l-1]
    result = prefix_sum[r] - prefix_sum[l-1]
    print(result)

算法及复杂度

算法：前缀和 (Prefix Sum)
时间复杂度： $O(n + m)$ 。其中 $O(n)$ 用于构建前缀和数组， $O(m)$ 用于回答 $m$ 次查询，每次查询 $O(1)$ 。
空间复杂度： $O(n)$ ，用于存储前缀和数组。