前缀和算法原理详解

一、问题背景

在处理数组区间查询时，如果我们需要频繁计算某一段连续元素的和（例如从第 l 个到第 r 个元素），直接遍历求和的时间复杂度是 O(n)。当查询次数 m 很大时，总耗时可能达到 O(n*m)，这在数据量较大（如 n, m ≤ 10^5）时会超时。

输入描述： 第一行包含两个整数 n, m (1 ≤ n, m ≤ 10^5)，分别代表数组长度和查询次数。 第二行包含 n 个整数 a_1, a_2, ..., a_n (-10^9 ≤ a_i ≤ 10^9)。 随后 m 行，每行包含两个整数 l, r (1 ≤ l ≤ r ≤ n)，表示一次查询。

输出描述： 对于每次查询，输出区间 [l, r] 的和。

示例： 输入：

3 2
1 2 4
1 2
2 3

输出：

3
6

二、算法原理

前缀和本质上是一种动态规划思想的简化应用。它的核心在于预处理，将重复计算转化为常数时间的查询。

1. 状态定义

我们定义一个前缀和数组 dp，其中 dp[i] 表示原数组中从第 1 个元素到第 i 个元素的累加和。

2. 状态转移

递推公式非常简单：

dp[i] = dp[i - 1] + arr[i]

这意味着，当前位置的前缀和等于'上一个位置的前缀和'加上'当前元素的值'。通过这种方式，我们只需要遍历一次数组，就能构建出整个前缀和表。

3. 区间查询优化

有了前缀和数组，计算任意区间 [l, r] 的和就变得异常简单。根据容斥原理：

Sum(l, r) = dp[r] - dp[l - 1]

这样，每次查询的时间复杂度降为 O(1)，整体复杂度优化为 O(n + m)。

注意： 在实际开发中，如果数组元素较大或累加次数多，前缀和数组建议使用 long 类型存储，防止整数溢出。

三、代码实现

下面是一个标准的 Java 实现示例。为了处理 1-based 索引的查询方便，我们在读取数组时通常从下标 1 开始填充。

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        
        // 读取数组长度 n 和查询次数 m
        int n = in.nextInt();
        int m = in.nextInt();
        
        // 使用 long 类型防止累加溢出
        // 下标从 1 开始，方便处理 l-1 的情况
        long[] dp = new long[n + 1];
        
        // 构建前缀和数组
        for (int i = 1; i <= n; i++) {
            int val = in.nextInt();
            dp[i] = dp[i - 1] + val;
        }
        
        // 处理 m 次查询
        while (m-- > 0) {
            int l = in.nextInt();
            int r = in.nextInt();
            
            // 利用前缀和公式 O(1) 计算区间和
            System.out.println(dp[r] - dp[l - 1]);
        }
        
        in.close();
    }
}

四、实战细节

1. 边界处理：注意题目中的索引是从 1 开始还是 0 开始。上述代码适配了常见的 1-based 输入，如果是 0-based 数组，公式需调整为 dp[r+1] - dp[l]。
2. 数据类型：当单个元素接近 10^9 且 n 达到 10^5 时，总和可能超过 2^31-1，务必使用 long。
3. 输入效率：在极端大数据量下（如 n=10^6），Scanner 可能会变慢，此时可考虑使用 BufferedReader 和 StringTokenizer。

通过这种预处理方式，原本需要大量循环的计算被压缩成了简单的减法运算，这就是前缀和算法的魅力所在。