前缀和与差分
从 LC 303 区域和检索开始：用一次 O(n) 预处理换回每次 O(1) 区间查询，再用差分把 O(qn) 的区间更新降到 O(n + q)。
1. 核心原理
前缀和（prefix sum） 是一种把"区间求和"转换成"两点相减"的预处理技巧。对长度 n 的数组 nums，定义 prefix[i] = nums[0] + nums[1] + … + nums[i-1]（prefix[0] = 0，长度 n + 1）。任意闭区间 [l, r] 的和等于 prefix[r + 1] - prefix[l]，单次查询 O(1)。差分（difference array） 是它的对偶：对 nums 的差分 diff 做一次前缀和恰好还原 nums；因而把"区间 [l, r] 全部加 v"压成"diff[l] += v; diff[r + 1] -= v"两次端点修改，单次 O(1)。
把这两件事写成一句：一次 O(n) 预处理换回单次 O(1) 的查询/更新。q 次操作的总成本从暴力 O(qn) 降到 O(n + q)。本节统一这套预处理模板（1D / 2D / 差分），后续把 LC 303 / 304 / 1109 / 560 / 974 / 1314 等题串成一族。
1.1 朴素做法的局限
对每次查询 sumRange(l, r) 现场扫一遍 [l, r]：单次 O(r - l + 1)，最坏 O(n)。q 次查询合计 O(qn)；当 n = q = 10⁴ 时是 10⁸ 操作，LeetCode 判题机已经在 TLE 边缘。对"区间加 + 一次最终值查询"题（如 LC 1109），逐条预订逐个累加同样是 O(qn)，2 × 10⁴ × 2 × 10⁴ = 4 × 10⁸，直接超时。两类朴素都把代价压在了"每次操作都要走遍区间"上。
1.2 关键洞察
求和与减法可交换：nums[l] + nums[l+1] + … + nums[r] = (nums[0] + … + nums[r]) - (nums[0] + … + nums[l-1])。把右边两段事先算好存起来，区间和就退化成两个预存值相减。这一观察有三条推论：
- 1D 前缀和：
prefix[i + 1] = prefix[i] + nums[i]，区间和sum[l..r] = prefix[r + 1] - prefix[l]。预处理O(n)，查询O(1)。 - 2D 前缀和：把"减一个区间"推广到"减一行带 + 减一列带 + 加回左上小角"的二维容斥。子矩阵
(r1, c1)..(r2, c2)的和 =P[r2+1][c2+1] - P[r1][c2+1] - P[r2+1][c1] + P[r1][c1]。 - 差分（前缀和的反向用法）：定义
diff[0] = nums[0]、diff[i] = nums[i] − nums[i − 1]（1 ≤ i < n），diff的前缀和恰好还原nums。把"区间[l, r]加v"压成diff[l] += v; diff[r + 1] -= v两次端点修改：nums[l − 1]不变、nums[l]变大v即diff[l] += v；nums[r]变大v、nums[r + 1]不变即diff[r + 1] -= v；区间内部相邻两数都+v，相减抵消，diff不变。所有修改完成后对diff做一次前缀和即得最终数组。
前缀和与差分构成一对互逆操作：前者把"区间求和"压成两点相减、优化查询，后者把"区间增减"压成两点改值、优化修改。一份模板正反各用一次。
第三条结合哈希表后还能解一类"和为 K 的子数组数"题（LC 560 / 974 / 1248）：固定右端 j，问题变成"左边出现过多少个 prefix[i] = prefix[j] - K"，扫一遍数组用哈希表计数即可。
1.3 模板要素
前缀和题的统一骨架由三件事决定：
- 下标偏移：
prefix长度n + 1，prefix[0] = 0作哨兵；区间和写prefix[r + 1] - prefix[l]。坚持 0-indexed 数组 + 1-indexed prefix 能消掉l == 0的边界判断。 - 维度 / 操作方向：一维 / 二维（容斥），查询 / 更新（差分），异或前缀和（XOR 自反性）。
- 是否配哈希表：题面是"和等于 K 的子数组数"或"和被 K 整除的子数组数"时，前缀和搭配
defaultdict(int)边扫边查；同余处理用((prefix % k) + k) % k兼容负数（Python 不需要，Java / C++ 需要）。
1.4 套路类型一览
| 套路 | 适用场景 | 代表题 |
|---|---|---|
| 1D 前缀和 | 区间和查询 | LC 303 / LC 525 |
| 2D 前缀和 + 容斥 | 子矩阵和查询 | LC 304 / LC 1314 / LC 363 |
| 差分（1D） | 大量区间加 + 最终一次查询 | LC 1109 / LC 1094 / LC 1854 |
| 前缀和 + 哈希表 | 和为 K / 和被 K 整除的子数组计数 | LC 560 / LC 974 / LC 1248 |
| 异或前缀和 | 子数组异或查询 / 子序列异或性质 | LC 1310 / LC 1442 / LC 1734 |
| 0/1 映射前缀和 | 把"奇偶 / 是否满足"压成 0/1 后接 LC 560 模板 | LC 1248 / LC 525 |
后续 §3 用 LC 303 切入 1D 模板，§4 把 1D / 2D / 差分三道母题串起来，§6 把前缀和与哈希表、二维容斥、最近边界预处理等组合招式扩展开。
1.5 两个常见变种
- 异或前缀和：把求和换成 XOR。由自反性
a ⊕ a = 0，xor[r + 1] ⊕ xor[l]等于子数组[l, r]的异或。LC 1310（子数组异或查询）、LC 1442（异或相等的三元组）、LC 1734（解码异或后的排列）都走这一套。 - 树上前缀和：把"线性前缀"换成"从根到当前节点的路径前缀"。配合 LCA，
路径(u, v) 的累计值 = pref[u] + pref[v] − 2 × pref[lca(u, v)]，可O(1)算任意两节点的路径求和 / 异或 / 计数。LCA 用倍增、Tarjan 离线、欧拉序 + RMQ 均可。代表题：LC 2477、LC 1372。
2. 通用模板
下面给出三种核心模板：1D 前缀和构造与查询、2D 前缀和（含容斥下标）、差分数组（区间加 + 一次还原）。三者用同一个"下标偏移"约定——前缀和数组比原数组多 1 位，prefix[0] = 0 当哨兵，区间右端写 r + 1。
# 模板 A：1D 前缀和
def build_prefix(nums: list[int]) -> list[int]:
n = len(nums)
prefix = [0] * (n + 1) # 哨兵 prefix[0] = 0
for i in range(n):
prefix[i + 1] = prefix[i] + nums[i]
return prefix
def range_sum(prefix: list[int], l: int, r: int) -> int:
"""闭区间 [l, r] 的和，0 <= l <= r < n"""
return prefix[r + 1] - prefix[l]
# 模板 B：2D 前缀和（多开一行一列哨兵 + 容斥）
def build_prefix_2d(mat: list[list[int]]) -> list[list[int]]:
m, n = len(mat), len(mat[0])
P = [[0] * (n + 1) for _ in range(m + 1)]
for i in range(m):
for j in range(n):
P[i + 1][j + 1] = (
P[i + 1][j] + P[i][j + 1] - P[i][j] + mat[i][j]
)
return P
def rect_sum(P, r1: int, c1: int, r2: int, c2: int) -> int:
"""子矩阵 (r1, c1) 到 (r2, c2) 之和（含两端）"""
return P[r2 + 1][c2 + 1] - P[r1][c2 + 1] - P[r2 + 1][c1] + P[r1][c1]
# 模板 C：差分数组（区间加 + 一次前缀和还原）
def apply_diff(n: int, updates: list[tuple[int, int, int]]) -> list[int]:
"""updates 每项 (l, r, v) 表示给 nums[l..r] 全部加 v（闭区间）"""
diff = [0] * (n + 1) # 多开 1 位避免 r+1 越界
for l, r, v in updates:
diff[l] += v # 区间起点 +v
diff[r + 1] -= v # 区间右端外 -v
nums = [0] * n
cur = 0
for i in range(n): # 一次前缀和还原
cur += diff[i]
nums[i] = cur
return nums// 模板 A：1D 前缀和
class PrefixSum {
private final int[] prefix;
PrefixSum(int[] nums) {
int n = nums.length;
prefix = new int[n + 1]; // 哨兵 prefix[0] = 0
for (int i = 0; i < n; i++) {
prefix[i + 1] = prefix[i] + nums[i];
}
}
int rangeSum(int l, int r) { // 闭区间 [l, r]
return prefix[r + 1] - prefix[l];
}
}
// 模板 B：2D 前缀和（容斥）
class Prefix2D {
private final int[][] P;
Prefix2D(int[][] mat) {
int m = mat.length, n = mat[0].length;
P = new int[m + 1][n + 1];
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
P[i + 1][j + 1] =
P[i + 1][j] + P[i][j + 1] - P[i][j] + mat[i][j];
}
}
}
int rectSum(int r1, int c1, int r2, int c2) {
return P[r2 + 1][c2 + 1] - P[r1][c2 + 1] - P[r2 + 1][c1] + P[r1][c1];
}
}
// 模板 C：差分数组
static int[] applyDiff(int n, int[][] updates) {
int[] diff = new int[n + 1]; // 多开 1 位
for (int[] u : updates) {
diff[u[0]] += u[2]; // 起点 +v
diff[u[1] + 1] -= u[2]; // 右端外 -v
}
int[] nums = new int[n];
int cur = 0;
for (int i = 0; i < n; i++) { // 一次前缀和还原
cur += diff[i];
nums[i] = cur;
}
return nums;
}// 模板 A：1D 前缀和
class PrefixSum {
vector<long long> prefix;
public:
PrefixSum(const vector<int>& nums) {
int n = nums.size();
prefix.assign(n + 1, 0); // 哨兵 prefix[0] = 0
for (int i = 0; i < n; i++) {
prefix[i + 1] = prefix[i] + nums[i];
}
}
long long rangeSum(int l, int r) const { // 闭区间 [l, r]
return prefix[r + 1] - prefix[l];
}
};
// 模板 B：2D 前缀和（容斥）
class Prefix2D {
vector<vector<long long>> P;
public:
Prefix2D(const vector<vector<int>>& mat) {
int m = mat.size(), n = mat[0].size();
P.assign(m + 1, vector<long long>(n + 1, 0));
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
P[i + 1][j + 1] =
P[i + 1][j] + P[i][j + 1] - P[i][j] + mat[i][j];
}
}
}
long long rectSum(int r1, int c1, int r2, int c2) const {
return P[r2 + 1][c2 + 1] - P[r1][c2 + 1] - P[r2 + 1][c1] + P[r1][c1];
}
};
// 模板 C：差分数组
vector<int> apply_diff(int n, const vector<array<int, 3>>& updates) {
vector<int> diff(n + 1, 0); // 多开 1 位
for (const auto& u : updates) {
diff[u[0]] += u[2]; // 起点 +v
diff[u[1] + 1] -= u[2]; // 右端外 -v
}
vector<int> nums(n);
int cur = 0;
for (int i = 0; i < n; i++) { // 一次前缀和还原
cur += diff[i];
nums[i] = cur;
}
return nums;
}四点需要注意：
- 下标偏移：
prefix长度必须是n + 1，不是n；区间和写prefix[r + 1] - prefix[l]。坚持"prefix[i]表示前i个元素之和"这一口径，所有公式只有r + 1一处偏移。 - 2D 容斥：四个角的下标在
{r1, r2 + 1}×{c1, c2 + 1}中取；含r2 + 1与c2 + 1的项符号为+，少一个的为-，两个都不含（即P[r1][c1]）为+。 - 差分别忘了还原：
diff本身不是答案，它的前缀和才是答案。漏掉最后那次cur += diff[i]的扫描，结果全错。 - 闭区间 vs 半开区间：差分模板里的
diff[r + 1] -= v是"闭区间转半开"的关键。若题面用半开区间[l, r)，直接diff[r] -= v不再+1；若题面用 1-indexed（如 LC 1109 的[first, last]），先在脑中转 0-indexed 再套模板。
3. 母题精讲
LeetCode 303. 区域和检索 - 数组不可变
链接：LeetCode 303
题意：给定一个整数数组 nums，实现一个 NumArray 类支持下面两个操作：
NumArray(int[] nums)：构造时收到numsint sumRange(int left, int right)：返回闭区间[left, right]的元素和（含两端）
nums 在初始化后不会被改写，但 sumRange 会被反复调用——题面里直接说明"最多 10⁴ 次调用"。
数据范围：
nums.length：1 到 10⁴nums[i]：−10⁵ 到 10⁵0 <= left <= right < nums.length- 调用
sumRange的次数：最多 10⁴
示例：
输入：
NumArray([-2, 0, 3, -5, 2, -1])
sumRange(0, 2)
sumRange(2, 5)
sumRange(0, 5)
输出：
1 // -2 + 0 + 3
-1 // 3 + (-5) + 2 + (-1)
-3 // 全部之和暴力解：每次查询扫一遍能 AC 吗？
最直觉的写法就是 sumRange 里现场循环累加：
class NumArray:
def __init__(self, nums: list[int]):
self.nums = nums
def sumRange(self, left: int, right: int) -> int:
s = 0
for i in range(left, right + 1):
s += self.nums[i]
return s构造 O(1)，单次查询 O(n)。q 次查询合计 O(qn)。
代入数据范围：n = q = 10⁴ 时最坏 10⁸ 次操作——LeetCode 判题机在边缘挣扎，遇到 left = 0、right = n−1 这种全段查询直接 TLE。
关键观察：查询的本质是两个端点相减
把 sumRange(left, right) 摊开成数学式：
sumRange(left, right) = nums[left] + nums[left+1] + ... + nums[right]
= (nums[0] + ... + nums[right]) − (nums[0] + ... + nums[left−1])事先把"从 0 累加到每个下标"的部分和预先算好存起来，那查询就退化成两个预存值相减——O(1)。预处理本身只扫一遍数组，O(n)。
q 次查询的总成本从 O(qn) 砍到 O(n + q)。代入 n = q = 10⁴：从 10⁸ 降到 2 × 10⁴，差出四个数量级。
这套权衡的关键变量是查询次数 q：
q很小（比如只查一次），预处理白费功夫，暴力反而更直接q大、或题目反复调用同一个对象（LC 303 就是这种）→ 预处理这步钱花得太值了
下面这个交互演示走一遍 [-2, 0, 3, -5, 2, -1] 的前缀和构造过程。红色是当前正在加进前缀和的位置，蓝色是已经累加完成的位置，金色高亮的是两道示例查询用到的端点：
prefix sum of [-2, 0, 3, -5, 2, -1]
prefix[i+1] = prefix[i] + nums[i]，最终 prefix = [0, -2, -2, 1, -4, -2, -3]
这就是前缀和。下面把它和它的对偶——差分——一起抽象出来。这两兄弟是同一套思路的正反两面，弄清一个另一个就跟着懂了。
4. 例题（三道）
下面三道按"维度递增 + 操作翻转"排：1D 求和 → 2D 求和 → 1D 区间加。这条递进里前两道用前缀和、最后一道翻面用差分——三段式把前缀和的两条路全走一遍。每道带 follow-up 直接续到下一题。
4.1 LC 303 区域和检索 - 数组不可变
链接：LeetCode 303
题意：实现 NumArray(nums) 与 sumRange(left, right)，返回闭区间 [left, right] 的元素和。nums 不会被改写，但 sumRange 反复调用。
数据范围：
nums.length：1 到 10⁴nums[i]：−10⁵ 到 10⁵- 调用
sumRange的次数：最多 10⁴
示例：
NumArray([-2, 0, 3, -5, 2, -1])
sumRange(0, 2) → 1
sumRange(2, 5) → -1
sumRange(0, 5) → -3构造时一次 O(n) 算好前缀和，每次查询 O(1)。
class NumArray:
def __init__(self, nums: list[int]):
n = len(nums)
self.prefix = [0] * (n + 1)
for i in range(n):
self.prefix[i + 1] = self.prefix[i] + nums[i]
def sumRange(self, left: int, right: int) -> int:
return self.prefix[right + 1] - self.prefix[left]class NumArray {
private final int[] prefix;
public NumArray(int[] nums) {
int n = nums.length;
prefix = new int[n + 1];
for (int i = 0; i < n; i++) {
prefix[i + 1] = prefix[i] + nums[i];
}
}
public int sumRange(int left, int right) {
return prefix[right + 1] - prefix[left];
}
}class NumArray {
vector<int> prefix;
public:
NumArray(vector<int>& nums) {
int n = nums.size();
prefix.assign(n + 1, 0);
for (int i = 0; i < n; i++) {
prefix[i + 1] = prefix[i] + nums[i];
}
}
int sumRange(int left, int right) {
return prefix[right + 1] - prefix[left];
}
};复杂度：构造 O(n)、单次查询 O(1)、空间 O(n)。
Follow-up：把数组升到二维矩阵呢——给一个 m × n 的矩阵，要求支持反复查询任意子矩阵的元素之和？
4.2 LC 304 二维区域和检索 - 矩阵不可变
链接：LeetCode 304
题意：实现 NumMatrix(matrix) 与 sumRegion(row1, col1, row2, col2)，返回从 (row1, col1) 到 (row2, col2) 的子矩阵的元素和（含两端）。matrix 不变，但 sumRegion 反复调用。
数据范围：
m, n：1 到 200matrix[i][j]：−10⁵ 到 10⁵0 <= row1 <= row2 < m，0 <= col1 <= col2 < n- 调用
sumRegion的次数：最多 10⁴
示例：
matrix = [
[3, 0, 1, 4, 2],
[5, 6, 3, 2, 1],
[1, 2, 0, 1, 5],
[4, 1, 0, 1, 7],
[1, 0, 3, 0, 5]
]
sumRegion(2, 1, 4, 3) → 8
sumRegion(1, 1, 2, 2) → 11
sumRegion(1, 2, 2, 4) → 12把 1D 前缀和搬到 2D 上，最大的区别在于：1D 上"区间和 = 右端前缀 − 左端前缀"只涉及两个值，2D 上要靠容斥——大矩形里减掉上面那条、再减掉左边那条，最后把被多减一次的左上角加回来。本质上还是"端点相减"的思想，只是端点从两个变四个。
col1 col2
┌───────┬─────────────────┬─────┐
row1 │ A │ B │ │
├───────┼─────────────────┤ │
│ │ │ │
│ C │ 目标 │ │
row2 │ │ 区域 │ │
├───────┴─────────────────┴─────┤
│ │
└───────────────────────────────┘
目标 = (A+B+C+目标) - (A+B) - (A+C) + A
= P[r2+1][c2+1] - P[row1][c2+1] - P[r2+1][col1] + P[row1][col1]构造时用递推 P[i+1][j+1] = P[i+1][j] + P[i][j+1] - P[i][j] + matrix[i][j]，同样是容斥的逆运用。
class NumMatrix:
def __init__(self, matrix: list[list[int]]):
m, n = len(matrix), len(matrix[0])
self.P = [[0] * (n + 1) for _ in range(m + 1)]
for i in range(m):
for j in range(n):
self.P[i + 1][j + 1] = (
self.P[i + 1][j]
+ self.P[i][j + 1]
- self.P[i][j]
+ matrix[i][j]
)
def sumRegion(self, row1: int, col1: int, row2: int, col2: int) -> int:
P = self.P
return (
P[row2 + 1][col2 + 1]
- P[row1][col2 + 1]
- P[row2 + 1][col1]
+ P[row1][col1]
)class NumMatrix {
private final int[][] P;
public NumMatrix(int[][] matrix) {
int m = matrix.length, n = matrix[0].length;
P = new int[m + 1][n + 1];
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
P[i + 1][j + 1] =
P[i + 1][j] + P[i][j + 1] - P[i][j] + matrix[i][j];
}
}
}
public int sumRegion(int row1, int col1, int row2, int col2) {
return P[row2 + 1][col2 + 1]
- P[row1][col2 + 1]
- P[row2 + 1][col1]
+ P[row1][col1];
}
}class NumMatrix {
vector<vector<int>> P;
public:
NumMatrix(vector<vector<int>>& matrix) {
int m = matrix.size(), n = matrix[0].size();
P.assign(m + 1, vector<int>(n + 1, 0));
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
P[i + 1][j + 1] = P[i + 1][j] + P[i][j + 1] - P[i][j] + matrix[i][j];
}
}
}
int sumRegion(int row1, int col1, int row2, int col2) {
return P[row2 + 1][col2 + 1] - P[row1][col2 + 1] - P[row2 + 1][col1] + P[row1][col1];
}
};复杂度：构造 O(mn)、单次查询 O(1)、空间 O(mn)。
容斥下标的记忆口诀：四个角都是 P[?][?]，行下标在 {row1, row2 + 1} 里选、列下标在 {col1, col2 + 1} 里选；含 row2 + 1 且含 col2 + 1 的取 +，恰好少一项的取 −，全都"−1"的（即 P[row1][col1]）取 +。
Follow-up：上面两道都是"只查询、不修改"。要是题目反过来——只做大量区间更新，最后只关心一次"全数组最终值"呢？这就该翻面用差分了。
4.3 LC 1109 航班预订统计
题意：有 n 个航班，编号从 1 到 n。给一个二维数组 bookings，每一项 [first, last, seats] 表示在航班 first 到航班 last（含两端）每个航班上预订了 seats 个座位。返回长度为 n 的数组 answer，answer[i] 是第 i + 1 个航班最终预订的总座位数。
数据范围：
n：1 到 2 × 10⁴bookings.length：1 到 2 × 10⁴bookings[i] = [first, last, seats]，1 <= first <= last <= n，1 <= seats <= 10⁴
示例：
输入：bookings = [[1,2,10],[2,3,20],[2,5,25]], n = 5
输出：[10, 55, 45, 25, 25]
解释（按航班 1..5）：
- 第 1 个航班：bookings[0] 贡献 10 → 10
- 第 2 个航班：bookings[0] 贡献 10 + bookings[1] 贡献 20 + bookings[2] 贡献 25 → 55
- 第 3 个航班：bookings[1] 贡献 20 + bookings[2] 贡献 25 → 45
- 第 4 个航班：bookings[2] 贡献 25 → 25
- 第 5 个航班：bookings[2] 贡献 25 → 25朴素做法：开一个长度 n 的数组 ans，对每条预订 [first, last, seats] 在 ans[first−1 .. last−1] 上逐个累加。单次区间加 O(n)，q = 2 × 10⁴ 条预订合计 O(qn) = 4 × 10⁸——上限拉满直接 TLE。
差分把这件事压到 O(n + q)，套路就三步：
- 用一个长度
n + 1的差分数组diff（多 1 位避免越界） - 对每条
[first, last, seats]，只改diff[first − 1] += seats与diff[last] -= seats（注意题目用 1-based 航班号，需要 −1 转 0-based） - 最后对
diff做一次前缀和，前n位就是答案
class Solution:
def corpFlightBookings(self, bookings: list[list[int]], n: int) -> list[int]:
diff = [0] * (n + 1) # 多开 1 位避免 last 越界
for first, last, seats in bookings:
diff[first - 1] += seats # 1-based → 0-based
diff[last] -= seats # last 对应 0-based 是 last - 1，
# 区间右端 +1 后就是 last
ans = [0] * n
cur = 0
for i in range(n):
cur += diff[i]
ans[i] = cur
return ansclass Solution {
public int[] corpFlightBookings(int[][] bookings, int n) {
int[] diff = new int[n + 1]; // 多开 1 位
for (int[] b : bookings) {
diff[b[0] - 1] += b[2]; // 1-based → 0-based
diff[b[1]] -= b[2]; // (last - 1) + 1 = last
}
int[] ans = new int[n];
int cur = 0;
for (int i = 0; i < n; i++) {
cur += diff[i];
ans[i] = cur;
}
return ans;
}
}class Solution {
public:
vector<int> corpFlightBookings(vector<vector<int>>& bookings, int n) {
vector<int> diff(n + 1, 0); // 多开 1 位
for (const auto& b : bookings) {
diff[b[0] - 1] += b[2]; // 1-based → 0-based
diff[b[1]] -= b[2]; // (last - 1) + 1 = last
}
vector<int> ans(n);
int cur = 0;
for (int i = 0; i < n; i++) {
cur += diff[i];
ans[i] = cur;
}
return ans;
}
};复杂度：时间 O(n + q)、空间 O(n)。
题目里 first / last 都是 1-based 航班号，这里最容易踩坑——-1 漏写或多写。我个人习惯先在脑子里把题面的 [first, last] 转换成 0-based 闭区间 [first − 1, last − 1]，再无脑套差分模板 diff[l] += v; diff[r + 1] -= v，得到 diff[first − 1] += v 和 diff[last] -= v，恰好对应上面的代码。"先归一化、再套模板"比"直接在头脑里调 +1 −1"稳得多。
5. 边界、易错与复杂度
prefix 数组到底开多长？
前缀和数组永远多开 1 位（哨兵 prefix[0] = 0）。这样区间公式 prefix[r + 1] − prefix[l] 没有边界分支。坚持 1-indexed 写 prefix[r] − prefix[l − 1] 也行，但遇到 l = 0 就要单独判断——多写一个 if，得不偿失。
模板里只要看到 prefix[i + 1] = prefix[i] + nums[i]，一定记得 prefix 长度是 n + 1，不是 n。这是前缀和最高频的 off-by-one。
2D 容斥下标怎么记
子矩阵 (r1, c1) .. (r2, c2)（含两端）的和：
P[r2 + 1][c2 + 1] - P[r1][c2 + 1] - P[r2 + 1][c1] + P[r1][c1]口诀：
- 大角（右下）+：
P[r2 + 1][c2 + 1] - 上边界（去掉顶行带）−：
P[r1][c2 + 1] - 左边界（去掉左列带）−：
P[r2 + 1][c1] - 左上小角 +：
P[r1][c1]（被前两项各减了一次，加回来一次）
+1 总是出现在 r2 和 c2 上，因为是闭区间 + 哨兵；r1 和 c1 永远是裸的，因为前一行/前一列才是要"挖掉"的边界。
差分别忘了还原
写差分时最容易犯的错就一句话：改完 diff 之后直接返回 diff 当答案。
diff 本身不是答案——diff 的前缀和才是答案。还原步骤永远是 cur += diff[i]; ans[i] = cur，一次线性扫。这一步漏了就全错。
也可以原地操作：for i in range(1, n): diff[i] += diff[i - 1]，最后 diff[0..n-1] 就是答案。但原地写法和"区间加端点 +v / −v"的写法容易在脑子里串线，新手我建议分两步走，写顺了再合。
区间是闭还是半开
文档里所有"区间 [l, r]"都是闭区间（含两端）——和 LC 303 / 304 / 1109 的题面一致。差分代码里的 diff[r + 1] -= v，"+1" 就是闭区间转换成"右端开"的关键——如果你的题面给的是半开区间 [l, r)，直接写 diff[r] -= v 即可，不要再 +1。
整数溢出
LC 1109 的极端输入：n = 2 × 10⁴、每条 seats ≤ 10⁴、q = 2 × 10⁴ 条预订。极端情况下某个航班可能被所有 q 条预订覆盖，单个 ans[i] ≤ q × 10⁴ = 2 × 10⁸——还在 int32 范围内（约 2.1 × 10⁹）。但相邻题（LC 1854、LC 2381 等差分变种）数值更大时，Java/C++ 要用 long，Python 无忧。
复杂度速查
| 题 | 预处理 | 单次查询/更新 | 空间 |
|---|---|---|---|
| LC 303 1D 前缀和 | O(n) | O(1) | O(n) |
| LC 304 2D 前缀和 | O(mn) | O(1) | O(mn) |
| LC 1109 1D 差分 | O(n + q)（含还原） | O(1) 更新 | O(n) |
7. 小结
前缀和把"区间求和"压成"端点相减"，差分把"区间加减"压成"端点改值"——两者互为逆操作。一句话，一次 O(n) 预处理换回每次 O(1) 查询，把 q 次操作从 O(qn) 降到 O(n + q)。
这套模板也是后面树状数组、线段树这些高级结构的认知起点——它们都是在"前缀和的查询"和"差分的更新"基础上加了"动态修改 + 高效区间和"的版本。下一节如果有兴趣可以直接翻 树状数组。