算法概念速查
什么是前缀和？区间和 O(1) 的原理、差分与经典例题
一句话定义
前缀和是把数组「先累加一遍存起来」的预处理技巧：令 pre[i] 表示前 i 个数之和（pre[0]=0），那么任意区间 [l, r] 的和等于 pre[r+1] − pre[l]，一次减法 O(1) 出结果，不必每问一次就从头加一遍。搭配哈希表，还能一遍扫完统计「和为 K 的子数组」的个数。
先打个比方
就像查电表：想知道 3 月用了多少度电，不需要把 3 月每天的用电量一天天加起来，拿 3 月底的表读数减去 2 月底的读数就行。电表本身就是「前缀和」——它记录的是从装表那天到现在的累计量，任何时间段的用量都是两次读数之差。
它是怎么运作的
「和为 K 的子数组」是前缀和的招牌打法：子数组 (l, r] 的和为 K 等价于 pre[r] − pre[l] = K，即 pre[l] = pre[r] − K。于是从左到右扫描，用哈希表记录每个前缀和出现的次数，每到一个位置就查「pre[r] − K 出现过几次」，查到几次就有几个以 r 结尾的合法子数组。含负数也完全不怕——这正是它比滑动窗口普适的地方。
差分是前缀和的逆运算：diff[i] = a[i] − a[i−1]，对区间 [l, r] 整体加 v 只需 diff[l] += v、diff[r+1] −= v 两个端点操作，全部修改做完后对 diff 求一遍前缀和即还原数组。大量区间批量加减时，从 O(n·q) 降到 O(n + q)。
什么时候用：识别信号
题目里出现下面任何一条，就该想到「前缀和」。
- 反复查询「某段区间的和」，而数组本身不变
- 统计「和为 K / 和能被 K 整除」的子数组个数——尤其含负数时
- 滑动窗口因为负数失去单调性做不了的题，前缀和 + 哈希表能接
- 对多个区间做批量加减、最后才问结果（差分的主场）
别和它们搞混
vs 滑动窗口
滑动窗口要求合法性单调，元素全非负才玩得转；前缀和不挑正负，只做代数变形。全正数求「最短/最长和达标子数组」用滑窗，含负数数「和恰好为 K」用前缀和 + 哈希。
vs 差分
一对互逆操作：前缀和把「改单点、查区间」做成 O(1) 查询；差分把「改区间、查单点」做成 O(1) 修改。记法：查区间用前缀和，改区间用差分。
vs 树状数组 / 线段树
前缀和的大前提是数组静态；一旦既要改又要查（动态），前缀和每改一次要重建 O(n)，此时才轮到树状数组或线段树登场。
配套动画题：眼见为实
每道题都有逐步交互动画，看着数据动起来，比读十遍文字都快。
常见追问
pre 数组为什么要多一位 pre[0] = 0？
为了让「从下标 0 开始的区间」也能统一用减法：区间 [0, r] 的和 = pre[r+1] − pre[0]。不留这一位，就得到处写 if 特判，还容易在「和为 K」里漏掉从头开始的子数组。
为什么「和为 K 的子数组」不能用滑动窗口？
数组含负数时窗口和不单调：右扩可能变小、左收可能变大，「大了收小了扩」的判断失灵。前缀和把问题变成「查差值」，跟单调性无关，所以负数无压力。
二维前缀和怎么记？
记「一加两减一补」：sum(x1,y1,x2,y2) = pre[x2+1][y2+1] − pre[x1][y2+1] − pre[x2+1][y1] + pre[x1][y1]。减重叠了的部分要补回来，画个矩形容斥图一眼就懂。