java中前缀和数组可将区间和查询从o(n)降至o(1)，预处理o(n)；prefix[i]表示nums[0..i-1]之和，prefix[0]=0，递推式为prefix[i]=prefix[i-1]+nums[i-1]。
Java 中通过构建前缀和数组（Prefix Sum Array），可以把多次区间和查询的时间复杂度从 O(n) 降为 O(1)，只需预处理一次 O(n) 时间。核心思想是：让 prefix[i] 表示原数组 nums[0..i-1] 的累加和（即前 i 个元素之和）。
构造前缀和数组
假设原数组为 int[] nums，长度为 n，我们定义长度为 n+1 的前缀和数组 int[] prefix = new int[n + 1]，其中：
-
prefix[0] = 0（空区间和） -
prefix[i] = nums[0] + nums[1] + ... + nums[i-1]（i ≥ 1） - 递推公式：
prefix[i] = prefix[i - 1] + nums[i - 1]
代码示例：
int[] nums = {2, 4, 1, 5, 3};
int n = nums.length;
int[] prefix = new int[n + 1];
for (int i = 1; i 用前缀和快速计算任意区间和
要求 nums[left..right]（含两端）的和，只需：
Alibabacloud Sdk Client Initialization For Java
下载
在 Java 中初始化和管理阿里云 SDK客户端。包括单例模式、线程安全、endpoint 与 region 配置、VPC 终端节点、同步与异步等。
sum(left, right) = prefix[right + 1] - prefix[left]- 因为
prefix[right + 1]包含nums[0..right]，prefix[left]包含nums[0..left-1]，相减即得nums[left..right]
例如：求 nums[1..3]（即 4 + 1 + 5 = 10）：
int left = 1, right = 3; int sum = prefix[right + 1] - prefix[left]; // prefix[4] - prefix[1] = 12 - 2 = 10
支持动态更新？注意局限性
标准前缀和数组适用于静态数组 + 多次查询场景。一旦原数组元素被修改，整个前缀和数组需重新构建（O(n)），不高效。
- 若需频繁单点更新 + 区间查询，应改用 树状数组（Fenwick Tree） 或 线段树（Segment Tree）
- 前缀和的优势在于实现极简、无额外依赖、缓存友好、常数小
封装成工具类提升复用性
可封装为一个轻量工具类，隐藏细节：
class PrefixSum {
private final int[] prefix;
<pre class="brush:java;toolbar:false;">public PrefixSum(int[] nums) {
int n = nums.length;
this.prefix = new int[n + 1];
for (int i = 1; i <p>}</p><p>// 使用
PrefixSum ps = new PrefixSum(new int[]{2, 4, 1, 5, 3});
System.out.println(ps.rangeSum(1, 3)); // 输出 10</p>Java免费学习笔记：立即使用
解锁 Java 大师之旅：从入门到精通的终极指南
