前缀和专题

开源地址

为了便于大家学习，所有实现均已开源。欢迎 fork + star~

https://github.com/houbb/leetcode

前缀和

前缀和（Prefix Sum）是一种常见的数组预处理技巧，主要用于 快速计算区间的累加和，大幅度优化原本需要 O(n) 时间的区间求和操作，将其降为 O(1)。

一、什么是前缀和？

对一个数组 nums = [a₀, a₁, a₂, ..., aₙ₋₁]，它的前缀和数组 prefixSum 定义为：

prefixSum[0] = 0 （有时也会直接等于 a₀，视实现方式而定）
prefixSum[1] = a₀
prefixSum[2] = a₀ + a₁
prefixSum[3] = a₀ + a₁ + a₂
...
prefixSum[i] = a₀ + a₁ + ... + a₍ᵢ₋₁₎

有了这个数组之后，就可以在 常数时间 内计算任意区间 [l, r] 的和：

sum(l, r) = prefixSum[r + 1] - prefixSum[l]

注意：这里的 prefixSum[i] 是前 i 个数的和，因此需要 从索引 1 开始存储原数组的前缀和，prefixSum[0] = 0。

在线可视化

前缀和

二、代码实现（以 Java 为例）

// 构建前缀和
int[] prefixSum = new int[nums.length + 1]; // 多开一位，prefixSum[0] = 0
for (int i = 0; i < nums.length; i++) {
    prefixSum[i + 1] = prefixSum[i] + nums[i];
}

// 查询区间和 [l, r]
int sum = prefixSum[r + 1] - prefixSum[l];

四、复杂度分析

构建：O(n)
区间查询：O(1)

相比直接遍历区间求和（O(n)），前缀和大大加快了查询速度。

五、注意事项

前缀和数组要多开一位，避免边界问题。
适合 频繁查询、但不修改数组的情况。
如果原数组频繁修改（如变动某个元素），需要重新计算前缀和。
- 这种场景建议用更强的数据结构：如树状数组、线段树。

六、例题推荐

好的，下面是补充了力扣题目难度的表格，每题都是前缀和或差分相关的经典题：

题目编号	名称	类型	难度
LC 303	区域和检索 - 数组不可变	基础前缀和	🟢 简单
LC 724	寻找数组的中心索引	前缀和判等	🟢 简单
LC 304	二维区域和检索 - 矩阵不可变	二维前缀和	🟡 中等
LC 560	和为 K 的子数组	前缀和 + HashMap	🔴 中等
LC 525	连续数组（0 和 1 数量相等）	差分 + 前缀和	🔴 中等

参考资料

https://leetcode.cn/problems/best-time-to-buy-and-sell-stock-with-transaction-fee/

前缀和专题
开源地址
前缀和
参考资料

【leetcode】46-Prefix Sum 力扣前缀和介绍