

一、问题背景
在处理数组区间查询时,如果我们需要频繁计算某一段连续元素的和(例如从第 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();
}
}


