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

题目链接

题目描述

给定一个长度为 $n$ 的数组，有 $q$ 次询问，每次询问一个区间 $[l, r]$ 的和。

解题思路

本题是静态区间求和问题，即数组本身不会发生改变。对于这类问题，最经典和高效的算法是前缀和。

前缀和的核心思想是预处理出一个数组，我们称之为前缀和数组 $S$ ，其中 $S[i]$ 记录了原数组从第 1 个元素到第 $i$ 个元素的累加和。 $S[i] = \sum_{j=1}^{i} A[j]$

为了方便计算，我们通常让前缀和数组的下标从 1 开始，并定义 $S[0] = 0$ 。这个前缀和数组可以在 $O(n)$ 的时间内通过一次遍历计算出来，递推公式为： $S[i] = S[i-1] + A[i]$

当我们需要查询任意区间 $[l, r]$ （下标从 1 开始）的和时，我们可以利用已经计算好的前缀和数组。区间 $[l, r]$ 的和等于 "前 $r$ 个元素的和" 减去 "前 $l-1$ 个元素的和"。用公式表示就是： $\text{sum}(l, r) = S[r] - S[l-1]$

这样，每次查询只需要进行一次减法操作，时间复杂度为 $O(1)$ 。

算法步骤：

创建一个长度为 $n+1$ 的前缀和数组 $S$ ，并初始化为 0。
遍历原数组，计算出所有的 $S[i]$ 。
对于每一次询问 $[l, r]$ ，直接计算 $S[r] - S[l-1]$ 并输出结果。

代码

c++
java
python

#include <iostream>
#include <vector>

using namespace std;

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

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

    // 前缀和数组，使用 long long 防止求和溢出
    vector<long long> s(n + 1, 0);
    for (int i = 1; i <= n; ++i) {
        int a;
        cin >> a;
        s[i] = s[i - 1] + a;
    }

    // 处理每次查询
    while (q--) {
        int l, r;
        cin >> l >> r;
        cout << s[r] - s[l - 1] << "\n";
    }

    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 q = sc.nextInt();

        // 前缀和数组，使用 long 防止求和溢出
        long[] s = new long[n + 1];
        for (int i = 1; i <= n; ++i) {
            s[i] = s[i - 1] + sc.nextInt();
        }

        // 处理每次查询
        for (int i = 0; i < q; ++i) {
            int l = sc.nextInt();
            int r = sc.nextInt();
            System.out.println(s[r] - s[l - 1]);
        }
    }
}

# 注意：牛客网的 Python I/O 较慢，对于大数据量可能会超时
# 使用下面的快速 I/O 模板可以提高效率
import sys

def main():
    # 读取第一行
    n, q = map(int, sys.stdin.readline().split())
    # 读取第二行数组
    a = list(map(int, sys.stdin.readline().split()))
    
    # 构建前缀和数组
    s = [0] * (n + 1)
    for i in range(n):
        s[i + 1] = s[i] + a[i]
        
    # 读取并处理所有查询
    # sys.stdin.readlines() 会一次性读取所有剩余行
    queries = sys.stdin.readlines()
    for line in queries:
        l, r = map(int, line.split())
        print(s[r] - s[l - 1])

if __name__ == "__main__":
    main()

算法及复杂度

算法：前缀和
时间复杂度： $O(n+q)$ 。其中 $O(n)$ 用于构建前缀和数组，之后的 $q$ 次查询每次只需要 $O(1)$ 的时间。
空间复杂度： $O(n)$ ，用于存储前缀和数组。