functions前缀和
前缀和题型：怎么识别、怎么讲、怎么练
前缀和最直接的价值是避免重复计算重叠区间。它和哈希表结合后，会从“求区间和”进化成“统计目标差值”的强力模式。
覆盖题量
35+
推荐起手
先判断只要前缀数组，还是要前缀和 + 哈希。
高频误区
区间端点的闭开关系混乱。
什么时候该想到这个模式
题目要处理很多区间求和或区间统计。
答案依赖两个累计状态之间的差。
子数组目标条件可以改写成 prefix[j] - prefix[i] = target。
下手前的检查清单
先判断只要前缀数组，还是要前缀和 + 哈希。
想让区间公式更干净时，前面加一个 0。
区间端点是闭区间还是半开区间，要说清楚。
模运算题里要记得处理负数归一化。
真正适合面试表达的解题步骤
1
先定义累计状态代表什么。
2
一趟扫描构造前缀。
3
把目标条件改写成两个前缀状态的差。
4
如果是计数题，注意哈希表是先查再存还是先存再查。
5
每一步都用 O(1) 的差值更新答案。
常见变体
区间查询
用前缀数组快速回答重复的区间查询。
前缀和 + 哈希
通过查找之前出现过的前缀状态来统计或定位子数组。
二维前缀和
压缩矩阵中的子矩形查询。
模板预览
Python公开预览
prefix = [0] * (len(nums) + 1)
for i, value in enumerate(nums):
prefix[i + 1] = prefix[i] + value
range_sum = prefix[r + 1] - prefix[l]
更像真实刷题路径的推荐题单
这组题不是随机罗列，而是按“先建立识别感，再补关键变体，最后上强度”去排，适合真的拿来做一轮 pattern 复习。
入门建立直觉
#303 Range Sum Query - Immutable
快速回答多个不可变数组区间和查询。
[l, r] 的区间和就是 prefix[r + 1] - prefix[l]。
入门建立直觉
#49 Group Anagrams
把互为字母异位词的字符串分组。
两个字符串能分到同一组，当且仅当它们标准化后的字符频次签名相同。
变体补齐关键状态
#238 Product of Array Except Self
返回除自身以外所有元素乘积组成的数组。
只要先算左侧乘积，再从右边扫一遍，就完全不需要除法。
变体补齐关键状态
#304 Range Sum Query 2D - Immutable
回答矩阵子矩形求和查询。
任意子矩形和都等于大前缀减去两块重叠区域，再加回公共角落。
高频难点压强练习
#560 Subarray Sum Equals K
统计和为 k 的子数组个数。
哈希表里存的是过去前缀和的出现次数，而不是区间本身。
高频难点压强练习
#974 Subarray Sums Divisible by K
统计和可以被 k 整除的子数组个数。
这里统计的不是前缀和值本身，而是前缀和的模值类别。
高频坑点
warning
区间端点的闭开关系混乱。
warning
计数题里哈希表更新时机写错。
warning
模值没有归一化，导致查找失败。
warning
明明更适合正数滑窗，却硬写成前缀和。
练习顺序建议
1
先做不可变数组区间和。
2
再做和为 k 的子数组。
3
然后补整除和取模类前缀题。
4
最后做树上前缀和或二维前缀和变体。