前缀和通过预处理数组实现O(1)区间求和：构建长度n+1的prefix数组，prefix[0]=0，prefix[i]=prefix[i-1]+nums[i-1]，则[left,right]和为prefix[right+1]-prefix[left]。
在 Java 中，前缀和是一种通过预处理数组来加速区间求和查询的常用技巧。核心思想是：预先计算一个新数组 prefix，其中 prefix[i] 表示原数组从索引 0 到 i（含）的所有元素之和。这样，任意区间 [left, right] 的和就能用一次减法在 O(1) 时间内得到。
构造前缀和数组
假设原始数组为 nums，长度为 n，我们构建长度为 n 的前缀和数组（0-indexed），或更常用的是长度为 n + 1 的“带哨兵”版本（避免边界特判）。推荐使用后者：
- 定义
prefix[0] = 0 - 对每个
i从 1 到n，令prefix[i] = prefix[i - 1] + nums[i - 1] - 此时
prefix[i]表示nums[0..i-1]的和
实现 O(1) 区间查询
给定查询区间 [left, right]（闭区间，0 ≤ left ≤ right
sum = prefix[right + 1] - prefix[left]
立即学习“Java免费学习笔记（深入）”；
这是因为：
-
prefix[right + 1]=nums[0] + ... + nums[right] -
prefix[left]=nums[0] + ... + nums[left - 1] - 相减后剩下
nums[left] + ... + nums[right]
Java 示例代码
以下是一个完整、可运行的示例：
<font size="2"><pre class="brush:php;toolbar:false;">public class PrefixSum {
private int[] prefix;
<pre class='brush:java;toolbar:false;'>public PrefixSum(int[] nums) {
int n = nums.length;
prefix = new int[n + 1];
for (int i = 1; i <= n; i++) {
prefix[i] = prefix[i - 1] + nums[i - 1];
}
}
// 查询 [left, right] 闭区间的和，O(1)
public int rangeSum(int left, int right) {
return prefix[right + 1] - prefix[left];
}
// 使用示例
public static void main(String[] args) {
int[] nums = {2, 1, 3, 5, 4};
PrefixSum ps = new PrefixSum(nums);
System.out.println(ps.rangeSum(1, 3)); // nums[1]+nums[2]+nums[3] = 1+3+5 = 9
System.out.println(ps.rangeSum(0, 4)); // 全数组和 = 15
}}
注意事项与扩展
前缀和适用于静态数组（不频繁修改）。若需支持单点更新，应考虑线段树或树状数组（Fenwick Tree）。
- 空间复杂度为 O(n)，时间复杂度：预处理 O(n)，每次查询 O(1)
- 注意索引越界检查（尤其在生产代码中应加入
if (left = nums.length || left > right)等校验） - 同样思路可推广至二维数组（二维前缀和），用于子矩阵求和
