算法基础:前缀和原理与 Java 实现
在处理数组区间查询问题时,如果数据量较大且查询频繁,直接遍历求和往往会导致超时。今天我们来聊聊一种经典优化技巧——前缀和(Prefix Sum),它能将区间查询的时间复杂度从 O(n) 降低到 O(1)。
问题描述
给定一个长度为 n 的整数数组 a,以及 m 次查询操作。每次查询给出两个参数 l 和 r,要求输出数组中第 l 个到第 r 个元素之和(即 a[l] + ... + a[r])。
输入格式:
- 第一行包含两个整数 n, m (1 ≤ n, m ≤ 10^5)
- 第二行包含 n 个整数 a[1]...a[n] (-10^9 ≤ a[i] ≤ 10^9)
- 接下来 m 行,每行两个整数 l, r (1 ≤ l ≤ r ≤ n)
输出格式:
- 对于每次查询,输出一行整数代表区间和。
示例: 输入:
3 2
1 2 4
1 2
2 3
输出:
3
6
核心思路
为什么需要前缀和?
假设我们直接对每个查询进行循环累加,最坏情况下每次查询都要遍历整个数组。当 n 和 m 都达到 10^5 级别时,总运算量可能接近 10^10,这在常规时限内是无法接受的。
前缀和的核心思想是预处理。我们预先计算出一个新数组 dp,其中 dp[i] 存储原数组从下标 1 到 i 的所有元素之和。
公式很简单:
dp[i] = dp[i - 1] + arr[i]
这样构建完成后,任意区间 [l, r] 的和就可以通过两次减法瞬间得出:
sum(l, r) = dp[r] - dp[l - 1]
这就好比我们在路上每隔一段距离标记累计里程,想知道某两站之间的距离,直接用后一站的里程减去前一站的里程即可,无需重新走一遍。
注意事项
- 索引处理:为了方便计算
dp[l-1],通常将前缀和数组设为 n+1 长度,且dp[0] = 0。这样即使 l=1,也能正常访问dp[0]。 - 数据类型:题目中单个元素最大为 10^9,若累加次数多,总和极易超出 32 位整数范围(约 2×10^9)。因此前缀和数组务必使用 long 类型。
代码实现
下面是一个完整的 Java 解决方案。注意这里使用了 Scanner 读取输入,并针对大输入场景做了基本的数据类型保护。
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
// 读取数组长度和查询次数
if (!in.hasNextInt()) ;
in.nextInt();
in.nextInt();
[] array = [n + ];
( ; i <= n; i++) {
array[i] = in.nextInt();
}
[] dp = [n + ];
( ; i <= n; i++) {
dp[i] = dp[i - ] + array[i];
}
(m > ) {
in.nextInt();
in.nextInt();
System.out.println(dp[r] - dp[l - ]);
m--;
}
in.close();
}
}


