前缀和数组是解决多次区间和查询的高效方法，通过预处理使每次查询降为o(1)；定义prefix[0]=0，prefix[i]为nums[0..i-1]之和，区间[l,r]和为prefix[r+1]−prefix[l]。

前缀和数组是解决区间和查询问题最直接高效的手段，尤其适合多次查询、数组不修改的场景。核心思路是用空间换时间：预处理出一个新数组，让每次查询从 O(n) 降到 O(1)。

什么是前缀和数组

前缀和数组 prefix[i] 表示原数组 nums[0..i-1] 的累加和（通常定义 prefix[0] = 0，长度比原数组多 1）。这样设计的好处是：区间 [l, r] 的和 = prefix[r+1] - prefix[l]，无需边界特判。

例如 nums = [2, 1, 3, 4]，则 prefix = [0, 2, 3, 6, 10]。查 [1,2]（即 nums[1]+nums[2]=1+3=4）→ prefix[3] - prefix[1] = 6 - 2 = 4。

如何构建前缀和数组

只需一次遍历，线性时间完成：

Alibabacloud Sdk Client Initialization For Java

在 Java 中初始化和管理阿里云 SDK客户端。包括单例模式、线程安全、endpoint 与 region 配置、VPC 终端节点、同步与异步等。

下载

• 初始化 prefix[0] = 0
• 对 i 从 1 到 n，执行 prefix[i] = prefix[i-1] + nums[i-1]
• Java 中推荐使用 int[] 或 long[]，若元素可能很大或查询频繁，优先用 long 避免溢出

怎么快速回答区间和查询

给定查询区间左闭右闭 [left, right]（0-indexed），直接套公式：

• sum = prefix[right + 1] - prefix[left]
• 确保 0 ≤ left ≤ right
• 不需要循环累加，也不依赖额外数据结构（如线段树、树状数组），代码简洁稳定

适用边界与注意事项

前缀和不是万能的，用前先确认：

• 原数组是否静态？如果频繁修改元素，每次改都要重建前缀和，O(n) 开销大 → 改用树状数组或线段树
• 内存是否允许？额外 O(n) 空间，一般可接受，但超大数据流场景需考虑滚动或离线处理
• 是否涉及动态区间？比如带更新的区间最值、区间异或等 → 前缀和不适用，需更高级结构

掌握这个模式后，LeetCode 上像 “区域和检索”、“和为 K 的子数组”、“连续的子数组和” 等题都能快速切入。关键不是背公式，而是理解 prefix[r+1] - prefix[l] 为什么恰好抵消掉前面部分——这才是前缀和的本质逻辑。

Java免费学习笔记：立即使用
解锁 Java 大师之旅：从入门到精通的终极指南