前缀和算法原理详解

一、问题背景

在处理数组区间查询时，如果我们需要频繁计算某一段连续元素的和（例如从第 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 {
        {
            (System.in);
        
        
           in.nextInt();
           in.nextInt();
        
        
        
        [] dp =  [n + ];
        
        
         (   ; i <= n; i++) {
               in.nextInt();
            dp[i] = dp[i - ] + val;
        }
        
        
         (m-- > ) {
               in.nextInt();
               in.nextInt();
            
            
            System.out.println(dp[r] - dp[l - ]);
        }
        
        in.close();
    }
}