区间问题表面上都在问“这一段的和是多少”或“这一段都加上多少”，但两类操作的重心恰好相反。前缀和把许多次查询共同依赖的历史累积起来，让一次区间查询变成两个边界值的相减；差分把一次覆盖一整段的更新压缩成两个边界事件，最后再统一还原。它们都不是某个题目的技巧，而是把“区间”改写成“边界”的一套坐标语言。
这一章用半开区间 [l, r) 统一一维、二维和可修改结构的叙述：左端属于区间，右端只是边界。这样，长度恒为 r - l，空区间自然是 l == r，相邻区间 [l, m)、[m, r) 不重不漏。读完后，应当能从操作类型判断是做前缀和、差分、正数滑动窗口，还是改用树状数组或线段树。
先把区间写成边界
设数组 a 的长度为 n，并约定所有外部接口均使用半开区间：
[l,r)={l,l+1,…,r−1},0≤l≤r≤n
这里的右端 r 不是最后一个元素的下标，而是最后一个元素之后的位置。这个看似微小的约定，能消除绝大部分 +1、-1：
[0, n) 恰好是整个数组；[i, i) 是合法的空区间，和为零；- 删除或拼接边界时无需转换；
- 前缀的“长度”与前缀数组的下标恰好相同；
- 差分的结束标记就落在
r，不必猜测是否还需要再加一。
算法题常把查询写成闭区间 [left, right]。处理时只有一个可靠动作：立刻翻译成 [left, right + 1)，并把转换固定在输入边界处。不要让一种函数同时混用两种坐标系；它会在数组末尾、单点区间和空数组上制造极难定位的错误。
一维前缀和：查询是两个前缀的差
定义与不变量
定义长度为 n + 1 的数组 pre：
pre[0]=0,pre[i+1]=pre[i]+a[i]
因此 pre[i] 表示前 i 个元素 a[0..i) 的和，而不是“下标 i 之前若干不清楚的元素”。对任意合法半开区间，望远镜相消给出：
i=l∑r−1a[i]=(a[0]+⋯+a[r−1])−(a[0]+⋯+a[l−1])=pre[r]−pre[l]
不变量是：构建结束后，pre[i] 永远等于原数组 [0, i) 的元素和。 查询只读取两个已经稳定的边界，不扫描区间内部，所以每次查询为 O(1)。初始化花 O(n) 时间与 O(n) 额外空间；若问题需要保留原数组，这个空间通常很值得。
图中 pre[4] 覆盖 a[0..4)，pre[1] 覆盖 a[0..1)；两者相减恰好留下 a[1..4)。这也是为什么 pre 必须有长度 n + 1：当查询触及数组末尾时，r == n 需要一个真实存在的 pre[n]。
可复用模板
下面的类把数据和查询统一为 long long，即使输入元素是 int，累加也不会在中间步骤先溢出。sum(l, r) 的契约是 [l, r)；非法边界通过异常暴露，而不是悄悄返回一个似乎合理的值。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
| #include <cstddef>
#include <stdexcept>
#include <vector>
class PrefixSum {
public:
explicit PrefixSum(const std::vector<int>& values)
: pre_(values.size() + 1, 0) {
for (std::size_t i = 0; i < values.size(); ++i) {
pre_[i + 1] = pre_[i] + values[i];
}
}
long long sum(std::size_t left, std::size_t right) const {
if (left > right || right >= pre_.size()) {
throw std::out_of_range("invalid half-open range");
}
return pre_[right] - pre_[left];
}
private:
std::vector<long long> pre_;
};
|
right >= pre_.size() 正是在检查 right > n：由于 pre_.size() == n + 1，right == n 合法。空数组也不需要特殊分支；它构造出单个元素 {0}，唯一合法查询是 [0, 0)。
LeetCode 303：Range Sum Query - Immutable
303 的名字已经给出关键条件：数组是 immutable。一次性构建前缀和之后，sumRange(left, right) 查询闭区间。题目接口仍是闭区间，但内部不要让闭区间扩散：把它当作 [left, right + 1) 查询即可。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
| #include <cstddef>
#include <vector>
class NumArray {
public:
explicit NumArray(std::vector<int> nums)
: pre_(nums.size() + 1, 0) {
for (std::size_t i = 0; i < nums.size(); ++i) {
pre_[i + 1] = pre_[i] + nums[i];
}
}
int sumRange(int left, int right) const {
const std::size_t begin = static_cast<std::size_t>(left);
const std::size_t end = static_cast<std::size_t>(right + 1);
return static_cast<int>(pre_[end] - pre_[begin]);
}
private:
std::vector<long long> pre_;
};
|
题目保证索引有效，故代码没有加入无关的输入恢复逻辑。实际工程中，如果 right 可能等于 INT_MAX，应先转为更宽的类型再加一；更常见的方案是直接把公开接口定义为半开区间，从类型与契约上杜绝这次加一。
前缀和不是“任意查询”的答案
前缀和缓存的是静态历史。若构建后修改 a[p] += delta，那么所有 pre[i] (i > p) 都需要同步加上 delta；单点修改最坏为 O(n)。因此前缀和适合“数组不变、查询很多”，而不适合“每次修改后还要继续查询”。后文会回到这个选型边界。
另一个常见误区是把前缀和当成滑动窗口的替代品。它可以在含负数的数组上回答任意固定区间和，却不能凭自身在 O(n) 内搜索“和至少为 target 的最短区间”；搜索还需要额外结构。若元素全为正数，窗口和对右扩、左缩具有单调性，应该优先使用/algo/two-pointers/中的滑动窗口，而不是枚举每个端点再套前缀和。
二维前缀和：矩形是四个左上前缀的容斥
从一条线到一个左上矩形
矩阵 a 有 rows 行、cols 列。为了继续让下标表示前缀长度，令：
pre[i][j]=0≤x<i,0≤y<j∑a[x][y]
所以 pre 的尺寸是 (rows + 1) × (cols + 1)，第 0 行与第 0 列全为零。构建 pre[i][j] 时，把新单元 a[i-1][j-1] 加进来：上方矩形 pre[i-1][j] 与左方矩形 pre[i][j-1] 都包含左上重叠部分 pre[i-1][j-1]，它被重复计算一次，必须减回去：
pre[i][j]=a[i−1][j−1]+pre[i−1][j]+pre[i][j−1]−pre[i−1][j−1]
这里的“减”不是记忆技巧，而是容斥原理：两个集合的并等于二者之和减去交集。二维前缀和正确性的核心不变量是：每个 pre[i][j] 都精确记录原矩阵左上角 [0,i) × [0,j) 的和。
半开矩形查询
对查询矩形 [r1, r2) × [c1, c2)，先从最大的左上前缀 pre[r2][c2] 出发：减去目标上方的 pre[r1][c2]，再减去目标左方的 pre[r2][c1]。左上角 [0,r1) × [0,c1) 被减了两次，最后补回：
query=pre[r2][c2]−pre[r1][c2]−pre[r2][c1]+pre[r1][c1]
如果把二维公式写错，最有效的检查不是盯着符号，而是给每一项上色：最大矩形保留为底图；上方与左方各减一次；它们的重叠区域被减了两次，因此必须加回一次。每项的坐标都应是一个边界，不是最后一个元素下标。
完整二维模板
模板支持空矩阵，也检查矩阵是否为矩形。构建时只读原矩阵，查询仍是 O(1)。这里返回 long long，因为一个 int 矩阵中成千上万个元素相加极易超过 32 位范围。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
| #include <cstddef>
#include <stdexcept>
#include <vector>
class MatrixPrefixSum {
public:
explicit MatrixPrefixSum(
const std::vector<std::vector<int>>& grid)
: rows_(grid.size()),
cols_(grid.empty() ? 0 : grid[0].size()),
pre_(rows_ + 1, std::vector<long long>(cols_ + 1, 0)) {
for (const std::vector<int>& row : grid) {
if (row.size() != cols_) {
throw std::invalid_argument("grid must be rectangular");
}
}
for (std::size_t i = 1; i <= rows_; ++i) {
for (std::size_t j = 1; j <= cols_; ++j) {
pre_[i][j] = grid[i - 1][j - 1] + pre_[i - 1][j];
pre_[i][j] += pre_[i][j - 1] - pre_[i - 1][j - 1];
}
}
}
long long sum(std::size_t r1, std::size_t c1,
std::size_t r2, std::size_t c2) const {
if (r1 > r2 || c1 > c2 || r2 > rows_ || c2 > cols_) {
throw std::out_of_range("invalid half-open rectangle");
}
return pre_[r2][c2] - pre_[r1][c2]
- pre_[r2][c1] + pre_[r1][c1];
}
private:
std::size_t rows_;
std::size_t cols_;
std::vector<std::vector<long long>> pre_;
};
|
注意 grid.empty() ? 0 : grid[0].size() 只在空矩阵时读取零列；非空但所有行均为空的矩阵也合法，cols_ == 0，所有合法查询的列边界只能是 0。很多实现把 matrix[0] 写在任何判断之前，因而在 LeetCode 304 的空输入变体或真实服务的空结果集上越界。
LeetCode 304：Range Sum Query 2D - Immutable
304 使用闭矩形 (row1, col1) 到 (row2, col2)。接口需要的只是输入翻译，数据结构本身无需为题目风格改变：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
| #include <cstddef>
#include <vector>
class NumMatrix {
public:
explicit NumMatrix(std::vector<std::vector<int>> matrix)
: rows_(matrix.size()),
cols_(matrix.empty() ? 0 : matrix[0].size()),
pre_(rows_ + 1, std::vector<long long>(cols_ + 1, 0)) {
for (std::size_t i = 1; i <= rows_; ++i) {
for (std::size_t j = 1; j <= cols_; ++j) {
pre_[i][j] = matrix[i - 1][j - 1] + pre_[i - 1][j];
pre_[i][j] += pre_[i][j - 1] - pre_[i - 1][j - 1];
}
}
}
int sumRegion(int row1, int col1, int row2, int col2) const {
const std::size_t r1 = static_cast<std::size_t>(row1);
const std::size_t c1 = static_cast<std::size_t>(col1);
const std::size_t r2 = static_cast<std::size_t>(row2 + 1);
const std::size_t c2 = static_cast<std::size_t>(col2 + 1);
const long long result = pre_[r2][c2] - pre_[r1][c2];
return static_cast<int>(result - pre_[r2][c1] + pre_[r1][c1]);
}
private:
std::size_t rows_;
std::size_t cols_;
std::vector<std::vector<long long>> pre_;
};
|
304 的约束保证矩阵是矩形且索引有效，所以这一版聚焦题意。若你的函数没有这种外部保证，优先复用前一节的检查版本。二维前缀和的构建为 O(rows⋅cols)，空间同阶；若只查询极少数矩形，预处理反而可能浪费，直接扫描小矩形更简单。预处理的价值来自大量、重复、不可修改的查询。
前缀和加哈希表：把“区间”改写成两个同余前缀
前两节的查询端点是外部给定的。还有一大类题目要求“统计有多少个子数组满足某个和”，端点未知，暴力枚举所有 [l, r) 会有 O(n2) 个候选。前缀和仍然能降维：
pre[r]−pre[l]=k⟺pre[l]=pre[r]−k
从左到右扫描右边界 r 时，只要知道此前每种前缀和出现了几次，就能立刻知道有多少个左边界 l 能与当前 r 配对。哈希表的键是前缀和，值是此前出现次数。
最重要的扫描顺序
对当前元素更新出 prefix 后，顺序必须是：
- 先读取
freq[prefix - k]，把此前可配对的前缀加入答案； - 再执行
++freq[prefix]，把当前前缀交给未来的右边界使用。
为什么不能反过来？当 k == 0 时，若先插入当前 prefix，当前边界会和自己配对，等价于把空区间 [r, r) 错算进答案。我们需要的左边界严格早于当前右边界，因此哈希表在查询时只能代表“过去”。
初始化 freq[0] = 1 同样不是模板装饰。它表示尚未取任何元素的空前缀 pre[0]，让从下标 0 开始、和为 k 的子数组自然满足 0 = prefix - k。没有它，所有前缀起点的答案都会漏掉。
LeetCode 560：Subarray Sum Equals K
数组可以有负数，故不能使用正数滑动窗口；窗口扩大时和不一定增加，缩小时也不一定减少。哈希前缀和不依赖元素符号，线性扫描即可统计所有连续子数组。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
| #include <unordered_map>
#include <vector>
int subarraySum(const std::vector<int>& nums, int target) {
std::unordered_map<long long, int> freq;
freq.reserve(nums.size() * 2 + 1);
freq[0] = 1;
long long prefix = 0;
int answer = 0;
for (int value : nums) {
prefix += value;
const auto found = freq.find(prefix - target);
if (found != freq.end()) {
answer += found->second;
}
++freq[prefix];
}
return answer;
}
|
复杂度是期望 O(n) 时间、O(n) 空间。reserve 不是正确性的必需品，却能降低大量不同前缀和时的重哈希次数；它不替代良好的哈希函数，也不改变最坏情况下哈希表可能退化的理论上界。prefix 使用 long long，因为即使答案受题目约束，途中累计值也可能溢出 int。
手算 nums = [1, 2, 1, 2, 1]、k = 3 时：扫描到第二个元素前缀为 3，读取 freq[0] 得到 [0,2)；扫描到第四个元素前缀为 6，读取 freq[3] 得到 [2,4)；扫描到第五个元素前缀为 7，读取 freq[4] 得到 [3,5)。每次都是“当前右边界”向历史索要所需的左边界。
LeetCode 525：Contiguous Array
525 表面上在问 0 和 1 数量相等的最长连续子数组。把 0 视为 -1、把 1 视为 +1 后，区间内 0、1 数量相同，等价于变换后区间和为 0：
count(1)−count(0)=0
这一次不再统计每个前缀出现次数，而是记录每个前缀和最早出现的位置。若同一前缀值在位置 i、j 出现，i < j，则 (i, j] 的变换和为零；固定 j 时，最早的 i 给出最大长度。因此第一次出现后绝不能覆盖。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
| #include <algorithm>
#include <unordered_map>
#include <vector>
int findMaxLength(const std::vector<int>& nums) {
std::unordered_map<int, int> first_index;
first_index.reserve(nums.size() * 2 + 1);
first_index[0] = -1;
int balance = 0;
int answer = 0;
for (int i = 0; i < static_cast<int>(nums.size()); ++i) {
balance += nums[i] == 1 ? 1 : -1;
const auto found = first_index.find(balance);
if (found != first_index.end()) {
answer = std::max(answer, i - found->second);
} else {
first_index[balance] = i;
}
}
return answer;
}
|
这里 first_index[0] = -1 是 0 长度前缀的坐标表示：若位置 i 的平衡值第一次回到 0，合法区间就是 [0, i + 1)，长度为 i - (-1)。注意 560 的 map 存“次数”，525 的 map 存“最早位置”；键都叫前缀和，但值的语义由题目目标决定，不能机械互换。
同一骨架还能处理什么
前缀和哈希的统一问题是：为每个右边界寻找满足某个代数关系的历史前缀。常见变体包括：
- 子数组和可被
k 整除：存储 prefix mod k 的频次，余数应规范到 [0, k)； - 和为零的最长子数组：记录每个前缀和最早位置；
- 0、1 数量相等：把一类映射为
+1，另一类映射为 -1； - 多类别计数相等：把若干计数差组成状态向量，状态相同意味着中段平衡；
- 二维子矩阵和等于目标：固定上下边界，把列和压成一维，再调用 560 的计数器。
不同于/algo/dp/中“状态转移依赖此前最优解”的动态规划，这里的哈希表不保存最优子结构；它保存的是历史前缀的可计数、可定位信息。相同的线性扫描外观，正确性来源完全不同：DP 靠转移覆盖所有状态，前缀哈希靠代数等价把一对端点化为一个键查询。
一维差分：更新是两个边界事件
从相邻变化量出发
给定数组 a，定义差分数组 diff：
diff[0]=a[0],diff[i]=a[i]−a[i−1](i>0)
它记录的不是每个位置的绝对值，而是从前一格移动到这一格时发生了多大变化。反过来，原数组可以通过一次前缀累加还原：
a[i]=j=0∑idiff[j]
现在把 [l, r) 的所有元素加上 delta。区间内部相邻两个位置同时增加 delta，它们的差不变；只有进入区间时产生一次 +delta，离开区间时产生一次 -delta：
diff[l]+=delta,diff[r]−=delta
若 r == n，结束事件仍需要一个落点，所以实际差分数组常分配为 n + 1。这不仅免去分支，也让“每个半开区间都在 r 停止”的规则不被数组末尾破坏。
这与前缀和形成漂亮的对偶：前缀和把“查询一个区间”化简为两个边界相减；差分把“更新一个区间”化简为两个边界修改。它们可以串联：先在差分上做许多 O(1) 更新，再一次前缀还原得到最终数组。
从零开始的区间加模板
下面的函数接收长度和若干半开更新，每条更新为 {left, right, delta}。它在差分数组上合并事件，最后一次扫描恢复结果。初始化是零数组时，diff[0] 不需要从任何基数组复制；若要在已有数组上更新，下一小节给出做法。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
| #include <cstddef>
#include <stdexcept>
#include <vector>
struct RangeAdd {
std::size_t left;
std::size_t right;
long long delta;
};
std::vector<long long> applyRangeAdds(
std::size_t size, const std::vector<RangeAdd>& updates) {
std::vector<long long> diff(size + 1, 0);
for (const RangeAdd& update : updates) {
if (update.left > update.right || update.right > size) {
throw std::out_of_range("invalid half-open range");
}
diff[update.left] += update.delta;
diff[update.right] -= update.delta;
}
std::vector<long long> values(size, 0);
long long running = 0;
for (std::size_t i = 0; i < size; ++i) {
running += diff[i];
values[i] = running;
}
return values;
}
|
这里可以放心写 diff[update.right]，因为尺寸是 size + 1。即使更新是 [0, size)，停止事件也落在合法的 diff[size]。还原循环只访问 0..size-1，因为输出数组没有位置 size；多出的哨兵格只承担“结束事件”的语义。
在已有数组上叠加更新
若基数组不是零，先构造它的差分：第一格为 base[0]，后续格为相邻差；然后继续在边界上合并事件，最后前缀还原。无需对每条更新逐格修改原数组。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
| #include <cstddef>
#include <stdexcept>
#include <vector>
struct RangeAdd {
std::size_t left;
std::size_t right;
long long delta;
};
std::vector<long long> addToBase(
const std::vector<int>& base,
const std::vector<RangeAdd>& updates) {
const std::size_t size = base.size();
std::vector<long long> diff(size + 1, 0);
if (!base.empty()) {
diff[0] = base[0];
}
for (std::size_t i = 1; i < size; ++i) {
diff[i] = static_cast<long long>(base[i]) - base[i - 1];
}
for (const RangeAdd& update : updates) {
if (update.left > update.right || update.right > size) {
throw std::out_of_range("invalid half-open range");
}
diff[update.left] += update.delta;
diff[update.right] -= update.delta;
}
std::vector<long long> result(size, 0);
for (std::size_t i = 0; i < size; ++i) {
result[i] = diff[i] + (i == 0 ? 0 : result[i - 1]);
}
return result;
}
|
空数组依然自然：没有访问 base[0]，所有合法更新只能是 [0,0)，返回空结果。不要为了“看起来通用”把 base[0] 无条件读取；空输入不是异常情况，而是半开区间系统中应被良好定义的零长度对象。
LeetCode 1109：Corporate Flight Bookings
1109 的预订 [first, last, seats] 是一组闭区间航班编号，且编号从 1 开始。将它翻译为零基半开区间是 [first - 1, last)：原来的最后一班 last 被包含，半开右端正好也写成 last。这个转换后，模板就完全不变。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
| #include <cstddef>
#include <vector>
std::vector<int> corpFlightBookings(
const std::vector<std::vector<int>>& bookings,
int flight_count) {
const std::size_t size = static_cast<std::size_t>(flight_count);
std::vector<long long> diff(size + 1, 0);
for (const std::vector<int>& booking : bookings) {
const std::size_t left =
static_cast<std::size_t>(booking[0] - 1);
const std::size_t right =
static_cast<std::size_t>(booking[1]);
const int seats = booking[2];
diff[left] += seats;
diff[right] -= seats;
}
std::vector<int> answer(size, 0);
long long running = 0;
for (std::size_t i = 0; i < size; ++i) {
running += diff[i];
answer[i] = static_cast<int>(running);
}
return answer;
}
|
题目保证每个 booking 有三个元素、编号范围有效且最终值可装入 int。在通用 API 中应先验证 booking.size() == 3 及转换前的正数范围，尤其不要把负数 booking[0] - 1 直接转换成 size_t；负数转为无符号数会变成巨大的下标。
二维差分：四个角记录一块矩形的开关
二维差分是“一维只改两个端点”的直积。要给半开矩形 [r1, r2) × [c1, c2) 统一加 delta，在差分矩阵的四个角标记：
diff[r1][c1]diff[r2][c1]diff[r1][c2]diff[r2][c2]+=delta,−=delta,−=delta,+=delta
可以把它看作两个一维停止规则的叠加：沿行方向进入后加、离开后减；沿列方向也进入后加、离开后减。右下角被两个“停止”影响，符号重新变成正号。四角的 + - - + 与二维前缀和的容斥符号完全同构，只是一个在编码更新，一个在解码累积。
二维还原公式
二维差分还原同样做二维前缀和：
value[i][j]=diff[i][j]+value[i−1][j]+value[i][j−1]−value[i−1][j−1]
为了让 r2 == rows 或 c2 == cols 的停止标记有位置，diff 的尺寸也要是 (rows + 1) × (cols + 1)。还原过程可原地覆盖 diff，随后只取左上 rows × cols；额外的末行、末列是边界事件缓冲，不属于最终矩阵。
完整的二维区间加类
MatrixRangeAdder 将更新阶段和还原阶段分开。调用若干次 add 后调用一次 materialize，得到最终矩阵；之后不再允许继续添加更新，避免调用者误以为结果仍会自动同步。若需要多批独立计算，创建新的实例比隐藏状态重置更清晰。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
| #include <cstddef>
#include <stdexcept>
#include <vector>
class MatrixRangeAdder {
public:
MatrixRangeAdder(std::size_t rows, std::size_t cols)
: rows_(rows), cols_(cols),
diff_(rows + 1, std::vector<long long>(cols + 1, 0)),
materialized_(false) {}
void add(std::size_t r1, std::size_t c1,
std::size_t r2, std::size_t c2, long long delta) {
if (materialized_) {
throw std::logic_error("updates are already materialized");
}
if (r1 > r2 || c1 > c2 || r2 > rows_ || c2 > cols_) {
throw std::out_of_range("invalid half-open rectangle");
}
diff_[r1][c1] += delta;
diff_[r2][c1] -= delta;
diff_[r1][c2] -= delta;
diff_[r2][c2] += delta;
}
std::vector<std::vector<long long>> materialize() {
if (materialized_) {
throw std::logic_error("materialize may be called once");
}
materialized_ = true;
for (std::size_t i = 0; i <= rows_; ++i) {
for (std::size_t j = 0; j <= cols_; ++j) {
if (i > 0) {
diff_[i][j] += diff_[i - 1][j];
}
if (j > 0) {
diff_[i][j] += diff_[i][j - 1];
}
if (i > 0 && j > 0) {
diff_[i][j] -= diff_[i - 1][j - 1];
}
}
}
std::vector<std::vector<long long>> result(
rows_, std::vector<long long>(cols_, 0));
for (std::size_t i = 0; i < rows_; ++i) {
for (std::size_t j = 0; j < cols_; ++j) {
result[i][j] = diff_[i][j];
}
}
return result;
}
private:
std::size_t rows_;
std::size_t cols_;
std::vector<std::vector<long long>> diff_;
bool materialized_;
};
|
这段还原循环的三个条件项是零边界的显式形式。另一种写法是额外再加一圈零边界，从 1 开始循环；两者都正确，但不要在同一实现中混用“diff 已有哨兵行列”与“循环又偏移一格”的坐标。二维题最常见的 bug 不是容斥本身，而是把原矩阵、前缀矩阵、差分矩阵各自多出的那一圈忘在不同地方。
二维差分的适用条件
二维差分的单次更新是 O(1)，所有更新后还原一次是 O(rows⋅cols)，空间也是同阶。它特别适合离线问题：航班、日期、棋盘覆盖、热力图标注、多个矩形叠加后只需最终状态。若每做一次矩形更新都要求立刻查询某个矩形和，差分会迫使你频繁还原，失去优势；这时应使用支持在线修改的结构。
二维差分还可以先把初始矩阵转换成二维差分，再把更新四角叠上去，最后还原。转换公式为：
diff[i][j]=a[i][j]−a[i−1][j]−a[i][j−1]+a[i−1][j−1]
越界项视为零。它是二维前缀公式的逆运算：一个保存“区域总量”，另一个保存“局部变化”。理解这对逆变换，比背下四角符号更可靠。
选型边界：先问操作，再选数据结构
前缀和、差分、滑动窗口看起来都在处理连续区间，却服务于不同的操作序列。判断的第一问不应是“这题像哪道模板”，而应是：输入是否可修改？更新和查询谁更多？元素符号是否提供单调性？答案是否必须在线给出？
静态区间和：前缀和
数组或矩阵固定、要回答很多范围和查询时，前缀和是最短且常数最小的方案。预处理后每次查询 O(1)，而且没有树状数组和线段树的复杂不变量。它还可以派生出“和为目标的子数组数量”“二维子矩阵和”等端点关系题。
但一旦更新插入查询序列，静态前缀和不再合适：更新一个位置会影响其后所有前缀。不要为了保留一个熟悉的模板而在每次更新后重建整个 pre；那是把数据结构选择错误藏在循环里。
批量区间加：差分
若操作是很多次区间加、最后只读取一次最终数组或最终矩阵，差分最合适：每次更新 O(1)，最后还原一次线性完成。它不提供快速的中途查询；还原前 diff[i] 只是变化量，不是位置值，直接把它当结果会得到局部跳变而非真实累计量。
“最后只读一次”是关键限定。若题目让你每次更新后都输出当前最大值，有时可以额外维护事件扫描或离线排序；若每次更新后都要任意范围和，则应转到在线结构，而不是重复前缀还原。
正数数组的最短/最长约束：滑动窗口
对于全为正数（或某些单调非负量）的数组，窗口和随着右端扩张不减，随着左端收缩不增。求“和至少为目标的最短子数组”“和不超过阈值的最长子数组”时，双指针能让左右边界都只前进，总时间 O(n)，空间 O(1)。这比“前缀和 + 二分”通常更直接。
一旦允许负数，窗口和不再单调：加一个负数可能使和变小，删一个负数反而使和变大。此时不要沿用滑窗的“违反约束就缩左端”规则；针对精确和的计数，使用前缀和哈希；针对更复杂的最短子数组和约束，往往需要单调队列、平衡树或其他题目特定结构。双指针的移动理由必须来自可证明的单调性，详见/algo/two-pointers/。
在线可修改的区间结构：树状数组与线段树
“在线”意味着更新与查询交错，且每个查询都必须立即看到此前更新。对于单点加、区间和，树状数组（Fenwick tree）是常用的 O(logn) 解；对于区间加、区间和，可以使用两棵树状数组；对于区间最值、区间赋值、懒标记组合，则通常选线段树。
以下双树状数组模板提供半开区间加与半开区间和。它不是前缀和或差分的替代写法，而是两者在“不断在线维护边界事件”时的升级：第一棵树维护差分事件，第二棵树维护事件乘位置的校正项。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
| #include <cstddef>
#include <stdexcept>
#include <vector>
class FenwickRangeSum {
public:
explicit FenwickRangeSum(std::size_t size)
: size_(size), bit1_(size + 1, 0), bit2_(size + 1, 0) {}
void addRange(std::size_t left, std::size_t right,
long long delta) {
checkRange(left, right);
add(bit1_, left + 1, delta);
add(bit1_, right + 1, -delta);
add(bit2_, left + 1, delta * static_cast<long long>(left));
add(bit2_, right + 1, -delta * static_cast<long long>(right));
}
long long sumRange(std::size_t left, std::size_t right) const {
checkRange(left, right);
return prefixSum(right) - prefixSum(left);
}
private:
void checkRange(std::size_t left, std::size_t right) const {
if (left > right || right > size_) {
throw std::out_of_range("invalid half-open range");
}
}
static void add(std::vector<long long>& bit,
std::size_t index, long long delta) {
while (index < bit.size()) {
bit[index] += delta;
index += index & (~index + 1);
}
}
static long long query(const std::vector<long long>& bit,
std::size_t index) {
long long result = 0;
while (index > 0) {
result += bit[index];
index -= index & (~index + 1);
}
return result;
}
long long prefixSum(std::size_t end) const {
const long long count = static_cast<long long>(end);
return count * query(bit1_, end) - query(bit2_, end);
}
std::size_t size_;
std::vector<long long> bit1_;
std::vector<long long> bit2_;
};
|
这里树状数组内部采用一基索引，外部仍是零基半开坐标。addRange(left, right, delta) 在内部的 left + 1 与 right + 1 放置差分事件；prefixSum(end) 返回外部 [0, end) 的和。index & (~index + 1) 等价于常见的 index & -index，但避免了对无符号 std::size_t 直接写一元负号。任何树状数组实现都必须保证更新循环的初始索引非零，否则 index += lowbit(index) 会永久停在 0。
线段树不应因为“功能更强”就默认选用。它代码长、常数大、懒标记容易错；当操作只是加法和求和时，树状数组更轻。只有需要区间最大/最小、区间赋值、复杂合并信息，或需要特定的更新查询组合时，再为线段树的通用性付出复杂度。
推导时怎样自检：从定义而不是公式开始
模板写得越熟，越容易在变体题里把正确公式套到错误坐标上。一个可靠的做法是把每个表项完整念出来，再检查边界是否满足这句话。
一维：前缀长度的归纳证明
对 pre[i] 的精确定义是“a 的前 i 个元素之和”。当 i == 0 时，空和为零，故 pre[0] = 0 正确。假设 pre[i] 已经代表 [0, i)，将下一个元素 a[i] 加入即可得到 [0, i + 1)：
pre[i+1]=pre[i]+a[i]
这也是循环为什么写作“读 values[i]、写 pre[i + 1]”，而不是把两者都写成 i。每一轮循环完成后，pre[0..i+1] 都已经满足定义；循环终止时，定义覆盖 0..n 的全部边界。
查询公式也可从“两个集合的差”而非记忆得到。[0,r) 包含 [0,l)，且两者的集合差就是 [l,r)；既然求和对不相交并集可加，就有 pre[r] = pre[l] + sum(l,r)。这种推导同时解释了为什么要求 l <= r：若边界倒置，两个前缀没有包含关系，差值虽有数值却不再表示普通区间和。
一个很小的手工用例足以发现大多数 off-by-one：
数组 a | pre | 查询 | 正确结果 |
|---|
[] | [0] | [0,0) | 0 |
[7] | [0,7] | [0,1) | 7 |
[7] | [0,7] | [1,1) | 0 |
[2,-3,5] | [0,2,-1,4] | [1,3) | 2 |
若某份实现无法让四行同时通过，不要立刻加条件分支；通常是 pre 的大小、查询右端或循环写入位置的语义错了一处。
二维：按格子验证容斥
二维公式最容易在行列或 +/- 上失手，可以不依赖任何图形地逐格分类。对 pre[r2][c2] 覆盖的每个单元 (x,y)，它可能位于四种区域：
| 单元位置 | 出现在 pre[r2][c2] | 减上方 | 减左方 | 加左上 | 最终系数 |
|---|
x < r1, y < c1 | +1 | -1 | -1 | +1 | 0 |
x < r1, c1 <= y < c2 | +1 | -1 | 0 | 0 | 0 |
r1 <= x < r2, y < c1 | +1 | 0 | -1 | 0 | 0 |
r1 <= x < r2, c1 <= y < c2 | +1 | 0 | 0 | 0 | +1 |
只有目标矩形中的格子以系数 1 留下，这就是公式的完整证明。二维差分的四角规则也能用同样的“固定一个格子、累积所有左上事件”检查：一个位置位于更新矩形内时，看到左上角的 +delta，不会越过任一停止边界；位置在右侧、下侧或右下时，至少被一个负角抵消，右下重叠又由正角补齐。
预处理、查询、答案的三个层次
前缀和题经常把这三层混为一谈：
- 预处理状态：
pre、二维 pre、diff 或哈希表； - 单次操作：一次范围和、一次矩形加、一次读取历史频次；
- 最终答案：查询返回值、还原数组、累计计数或最优长度。
例如 560 中的 prefix 是扫描过程的当前状态，freq 是历史状态摘要，answer 才是最终答案；它们都可能是 long long 或 int，但语义不同。再如差分题的 diff 不是“尚未完成的答案数组”，它是事件日志；只有前缀还原后才成为位置值。先分清这三层，再设计循环，能避免把“更新答案”与“更新数据结构”写成错误的顺序。
更多前缀状态变体
“前缀和”中的“和”可以替换为任何可逆或可比较的前缀状态。核心条件不是数组元素必须是数字，而是希望一个区间状态能由两个前缀状态迅速组合或判定。
前缀异或：相同规律，不同运算
异或满足结合律、交换律，且每个数是自己的逆元。因此定义：
px[0]=0,px[i+1]=px[i]⊕a[i]
便有：
a[l]⊕a[l+1]⊕⋯⊕a[r−1]=px[r]⊕px[l]
与加法前缀和不同，异或不需要减法；同一个值异或两次会消掉。若问题是“有多少个子数组异或为 target”，扫描时寻找的历史状态是 prefix_xor ^ target，顺序仍然是先查询频次、后插入当前状态。以下函数与 560 的结构几乎一致，只是代数关系变为异或。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
| #include <unordered_map>
#include <vector>
long long countSubarraysWithXor(
const std::vector<int>& nums, int target) {
std::unordered_map<int, long long> freq;
freq.reserve(nums.size() * 2 + 1);
freq[0] = 1;
int prefix_xor = 0;
long long answer = 0;
for (int value : nums) {
prefix_xor ^= value;
const auto found = freq.find(prefix_xor ^ target);
if (found != freq.end()) {
answer += found->second;
}
++freq[prefix_xor];
}
return answer;
}
|
这类变体提醒我们：不要因为题名里没有“sum”就放弃前缀思路。只要区间量可写成“前缀状态 A 与前缀状态 B 的关系”，就可能可以把枚举两端点降成扫描一个端点。
前缀计数差：多种类别的平衡
525 把二元类别转成一个平衡值。若有三类字符，希望区间内三种数量相等，可以固定其中一类为基准，记录两个差值，例如：
state=(count(A)−count(C), count(B)−count(C))
两处前缀状态完全相同，表示中间区间三类的增量相同。此时哈希键不再是一个整数，而是一个二元组；对于最长长度，仍记录最早出现位置；对于数量统计，仍记录频次。状态维度随类别数增长，空间和哈希成本也会增长，因此应确认问题真的需要全量状态，而不是可以借助排序、计数或窗口条件简化。
下面展示最长“a、b、c 数量相同”子串的完整写法。State 的相等关系和哈希必须同时定义，且键保存的是差值，不是三个绝对计数。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
| #include <algorithm>
#include <cstddef>
#include <string_view>
#include <unordered_map>
struct BalanceState {
int a_minus_c;
int b_minus_c;
bool operator==(const BalanceState& other) const {
return a_minus_c == other.a_minus_c
&& b_minus_c == other.b_minus_c;
}
};
struct BalanceStateHash {
std::size_t operator()(const BalanceState& state) const {
const std::size_t first =
static_cast<std::size_t>(
static_cast<unsigned>(state.a_minus_c));
const std::size_t second =
static_cast<std::size_t>(
static_cast<unsigned>(state.b_minus_c));
return first * 1000003U ^ second;
}
};
int longestBalancedABC(std::string_view text) {
std::unordered_map<BalanceState, int, BalanceStateHash> first;
first.reserve(text.size() * 2 + 1);
first[{0, 0}] = -1;
BalanceState state{0, 0};
int answer = 0;
for (int i = 0; i < static_cast<int>(text.size()); ++i) {
if (text[i] == 'a') {
++state.a_minus_c;
} else if (text[i] == 'b') {
++state.b_minus_c;
} else if (text[i] == 'c') {
--state.a_minus_c;
--state.b_minus_c;
}
const auto found = first.find(state);
if (found != first.end()) {
answer = std::max(answer, i - found->second);
} else {
first.emplace(state, i);
}
}
return answer;
}
|
函数把非 a/b/c 字符视为状态不变，因此它们可被包含在平衡子串内；若题目要求输入只能含三类字符，应该在调用边界验证或把 else 改为拒绝输入。算法设计中这类“未定义字符如何处理”属于接口契约，不应由哈希表的偶然行为决定。
前缀最值不是可相减前缀
并非所有聚合都能通过两个前缀相减得到区间答案。最小值、最大值、按位或、最大公约数都没有普通减法逆元；存储 prefix_max 后，prefix_max[r] 无法删除 [0,l) 的影响。对静态区间最值可用稀疏表，对在线更新可用线段树；对某些可逆运算如异或可用前缀结构。这个区分非常重要：不要看到“区间”就盲目创建 pre，先确认操作能否从两个前缀恢复。
差分的叠加性与离线视角
差分真正强大的原因不只是一条更新公式，而是线性叠加。若有多次更新 (lt,rt,deltat)，对某个位置 i，还原后的值为：
t∑deltat⋅[lt≤i<rt]
其中方括号是指示函数。每一条更新在 l_t 放入开始事件、在 r_t 放入结束事件；扫描到 i 时，所有尚未结束的事件之和恰好就是上式。这解释了为什么更新的输入顺序无关，也解释了为什么可以先把几百万条更新压进 diff，最后仅扫描一次。
用事件扫描理解最大重叠
有些题目不需要恢复每个位置，而是要找最多有多少区间同时覆盖一个点，例如会议室容量、航班座位峰值、时间线上并发任务。若坐标可压缩到数组下标，差分还原过程中的 running 最大值就是答案；无需真的保存完整 values。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
| #include <algorithm>
#include <cstddef>
#include <stdexcept>
#include <vector>
struct RangeAdd {
std::size_t left;
std::size_t right;
long long delta;
};
long long maxConcurrentCoverage(
std::size_t size, const std::vector<RangeAdd>& intervals) {
std::vector<long long> diff(size + 1, 0);
for (const RangeAdd& interval : intervals) {
if (interval.left > interval.right || interval.right > size) {
throw std::out_of_range("invalid half-open range");
}
diff[interval.left] += interval.delta;
diff[interval.right] -= interval.delta;
}
long long running = 0;
long long maximum = 0;
for (std::size_t i = 0; i < size; ++i) {
running += diff[i];
maximum = std::max(maximum, running);
}
return maximum;
}
|
若每个区间的 delta 均为 1，maximum 是覆盖数。半开区间还有一个现实含义：在同一时刻结束的任务与开始的任务不冲突，结束事件落在右边界，开始事件也落在该边界；数组差分的相加顺序自动体现了 [start,end) 的约定。若业务采用两端都闭合的离散日期，需要先明确“结束日是否占用”，再选择 right 还是 right + 1 放置结束事件。
坐标很大时：先离散化，再差分
差分数组需要连续下标。若区间端点是时间戳、经纬度或达到 109 的坐标，直接分配数组不可行，但只要最终答案只在事件边界之间变化，便可以坐标离散化：收集所有 left 与 right，排序去重，用其秩代替原坐标。更新仍只改两个秩位置。
注意离散化后的“一个格子”通常代表一段原坐标，而不是一个单位长度。若目标是最大覆盖次数，秩之间的物理长度无关；若目标是加权面积、区间总长度或对每个整数位置累加，扫描相邻离散坐标时必须乘上真实跨度 coords[i + 1] - coords[i]。离散化不是把大坐标粗暴变小，而是保留所有会改变状态的边界。
差分不适合的更新类型
普通差分擅长“区间全体加同一个值”，因为区间内部的相邻差不变。若更新是区间乘法、区间取最小值、区间赋值或按位置递增，边界事件不再只需要两个标记：
- 区间等差加法可以维护两层差分，或把贡献拆为斜率与截距；
- 区间赋值会覆盖此前事件，通常要线段树懒标记；
- 区间
chmin/chmax 需要更复杂的数据结构与不变量； - 每次更新后立即查询则需要在线结构，即使更新本身仍是加法。
选择差分的依据是“更新对区间内部变化量是否保持局部简单”，不是“更新的名字里是否有区间”。把不适合的操作硬塞进差分，常会产生大量补丁分支，最终既不快也不可靠。
由题目语言反推工具的决策流程
遇到数组或矩阵题时，可以按以下顺序提问，而不是先在脑中搜索题号：
- 查询还是更新？ 仅查询静态数据，考虑前缀和；仅更新并在最后输出，考虑差分。
- 端点已给定吗？ 已给定范围和直接前缀相减；端点未知但满足精确代数关系，考虑前缀状态加哈希。
- 元素是否保证非负或正？ 若窗口量随边界单调，考虑滑动窗口；含负数时不要依赖窗口缩扩的直觉。
- 操作是否交错在线出现？ 是则升级为树状数组、线段树或题目专用数据结构。
- 是一维还是二维？ 二维把“两个端点”变成“四个角”；先分配好额外的一行一列，再写容斥。
- 题目使用的区间制式是什么？ 闭区间、一基编号、行列坐标都只在输入输出处转换，内部始终用半开零基。
例如，“给定不可变矩阵，回答十万次子矩形和”在第一步已指向二维前缀和；“给定十万次矩形加，最后打印棋盘”指向二维差分；“更新和查询交替，查询区间最小值”则根本不应停留在前缀/差分族。这个流程的价值在于先排除错误工具，再精化实现细节。
复杂度对照
| 场景与结构 | 构建/单次更新 | 单次查询 | 空间 | 典型前提 |
|---|
| 一维静态前缀和 | 构建 O(n) | 区间和 O(1) | O(n) | 数据不修改、查询多 |
| 二维静态前缀和 | 构建 O(rc) | 矩形和 O(1) | O(rc) | 矩阵不修改、查询多 |
| 前缀和 + 哈希 | 扫描 O(n) | 扫描中统计 | O(n) | 端点未知、需满足代数关系 |
| 一维差分 | 每次区间加 O(1) | 最后还原 O(n) | O(n) | 批量更新、最后读取 |
| 二维差分 | 每次矩形加 O(1) | 最后还原 O(rc) | O(rc) | 批量矩形更新、最后读取 |
| 正数滑动窗口 | 扫描 O(n) | 扫描中求最值 | O(1) | 窗口量对边界单调 |
| 树状数组 | 更新 O(logn) | 区间和 O(logn) | O(n) | 在线加法/求和 |
| 线段树 | 更新 O(logn) | 查询 O(logn) | O(n) | 在线复合区间操作 |
其中 r、c 分别为矩阵行数与列数。复杂度表的目的不是背答案，而是在读题时迅速淘汰不匹配的工具：静态查询选前缀和；离线覆盖选差分；正数窗口约束选滑窗；更新查询交错选在线树结构。
容易失分的陷阱清单
- 累加溢出。
int 元素并不意味着前缀和能放进 int。构建 pre、diff、运行和、哈希键以及树状数组节点都应优先使用 long long；转换发生得越晚越安全。二维中元素数量相乘，风险更高。 - 忘记
pre[0]。 pre[0] = 0 是空前缀，不是多余位置。它让 [0, r) 的查询无需特判，也让 560 的 freq[0] = 1 能统计从第 0 个元素开始的子数组。 - 空数组访问第一个元素。
values[0]、matrix[0]、base[0] 都必须在确认非空后读取。正确的 n + 1 前缀和与差分表示能自然定义空输入，不需要伪造一个元素。 - 半开边界与闭区间混用。
[l, r) 的查询是 pre[r] - pre[l]；闭区间 [left, right] 必须在入口翻译为 [left, right + 1)。1109 的一基闭区间 [first,last] 翻译为零基半开 [first - 1,last)。 - 差分忘记结束事件。 区间加不是只做
diff[l] += delta；必须同时 diff[r] -= delta。分配 n + 1 长度后，即使 r == n 也要写入结束标记。 - 哈希表更新顺序颠倒。 对 560，先读
freq[prefix - k]，后写 freq[prefix]。否则 k == 0 时会把当前空区间计数。对 525，首次位置一旦记录就不能覆盖。 - 二维容斥符号错位。 最大矩形减上、减左、加左上；二维差分四角为
+ - - +。若某一项缺失，重叠区域会被多算或少算。 - 二维维度少一圈。 二维
pre 和 diff 都需要 (rows + 1) × (cols + 1) 的边界空间。行数与列数不能互换；查询先传行边界再传列边界，并坚持 [r1,r2) × [c1,c2)。 - 把差分数组直接当答案。
diff 是相邻变化量，只有经过一维或二维前缀还原才是最终值。多个更新可以先全部叠加，不能每次更新都把“还原结果”再当差分继续随意修改。 - 对有负数的和问题滥用滑动窗口。 窗口移动缺少单调依据时，局部缩扩无法保证不漏解；精确和计数应回到前缀和哈希，其他约束要重新推导不变量。
小结
前缀和与差分的共同语言是边界：
- 前缀和把区间查询变成
pre[r] - pre[l]； - 二维前缀和以四个左上前缀做容斥；
- 前缀和加哈希把未知左端点变成对历史前缀状态的查询，且必须先查后写；
- 差分把区间更新变成开始
+delta 与结束 -delta 两个事件； - 二维差分用四角标记矩形更新，再做二维前缀还原；
- 静态查询、离线更新、正数窗口、在线更新查询分别对应不同的数据结构边界。
真正应记住的不是某一行模板，而是每个数组下标的语义：前缀数组的下标是“已经取了多少个元素”，差分数组的值是“跨过这个边界时发生什么变化”。一旦把区间固定成半开坐标，公式、实现、空输入和数组末尾都会自然对齐；题目换成矩形、哈希计数或在线树结构时，仍能从同一套不变量出发推导答案。
