区间问题为什么需要预处理
很多题都会反复问同一类问题：某个区间的和是多少，某个矩形里的数是多少，很多次区间加法之后每个位置是多少。
如果每次都从头扫一遍，复杂度很容易变成 O(nq)。当 n 和 q 都到 1e5 时，这就不可接受了。
前缀和与差分解决的就是这种重复劳动。前缀和偏向查询，差分偏向修改。
一维前缀和
一维前缀和的定义很简单：
prefix[i] = a[1] + a[2] + ... + a[i]写代码时，我更喜欢用 1 下标，这样区间 [l, r] 的和就很顺手：
vector<long long> pre(n + 1, 0);
for (int i = 1; i <= n; i++) {
pre[i] = pre[i - 1] + a[i];
}
long long rangeSum(int l, int r) {
return pre[r] - pre[l - 1];
}预处理一次是 O(n)，之后每次区间求和是 O(1)。这就是前缀和最直接的价值。
什么时候想到前缀和
看到这些关键词，可以先想前缀和：
- 多次查询区间和；
- 连续子数组、连续区间；
- 求某段的平均值、总贡献、数量；
- 固定右端点，快速知道左边某段信息；
- 子数组和等于某个值。
前缀和不一定只存“和”。只要信息可以通过前缀相减得到，就可以考虑前缀数组。比如字符出现次数、某类元素个数、奇偶数量，都可以做成前缀统计。
前缀和加哈希
有些题不是问一个固定区间，而是问有多少个子数组满足某个条件。比如子数组和等于 k。
如果当前前缀和是 sum，想找一个以前的位置 j，让 sum - pre[j] = k，也就是 pre[j] = sum - k。所以可以用哈希表记录以前出现过的前缀和。
long long ans = 0, sum = 0;
unordered_map<long long, int> cnt;
cnt[0] = 1;
for (int x : a) {
sum += x;
if (cnt.count(sum - k)) ans += cnt[sum - k];
cnt[sum]++;
}这类写法很重要，因为它把“枚举左右端点”变成了“枚举右端点，再查需要的左端点”。
二维前缀和
二维前缀和用来快速求矩形区域的和。设 s[i][j] 表示左上角到 (i, j) 这个矩形的总和：
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) {
s[i][j] = s[i - 1][j] + s[i][j - 1] - s[i - 1][j - 1] + a[i][j];
}
}查询 (x1, y1) 到 (x2, y2) 的矩形和：
long long query(int x1, int y1, int x2, int y2) {
return s[x2][y2] - s[x1 - 1][y2] - s[x2][y1 - 1] + s[x1 - 1][y1 - 1];
}二维前缀和最容易错的是容斥里的加减号。可以把它理解成：先取大矩形，再减掉上面和左边多出来的部分，因为左上角被减了两次，所以要加回来一次。
一维差分
前缀和适合“多次区间查询”。差分适合“多次区间修改”。
如果要把区间 [l, r] 每个数都加上 x，直接改是 O(n)。用差分数组，只要改两个点：
diff[l] += x;
diff[r + 1] -= x;所有修改做完以后，再做一次前缀累加，还原最终数组：
for (int i = 1; i <= n; i++) {
diff[i] += diff[i - 1];
a[i] += diff[i];
}这背后的想法是：在 l 位置开始增加，在 r + 1 位置停止增加。
二维差分
二维差分处理的是矩形区域整体加值。给矩形 (x1, y1) 到 (x2, y2) 加上 v：
d[x1][y1] += v;
d[x2 + 1][y1] -= v;
d[x1][y2 + 1] -= v;
d[x2 + 1][y2 + 1] += v;最后对差分数组做二维前缀和，就能得到每个格子的最终增量。
二维差分不需要一开始就背得很熟。先把一维差分理解成“从这里开始影响，到那里结束影响”，再看二维版本，就会发现它其实是在四个角上控制影响范围。
这一篇先记住什么
- 前缀和：预处理一次，让区间查询变快。
- 差分：延迟结算，让区间修改变快。
- 一维问题先想 1 下标，能少掉很多边界烦恼。
- 遇到子数组和、区间和、矩形和、批量区间加法，先看看能不能用这两个工具。
下一篇写双指针和滑动窗口。它们解决的是另一类问题：如何让左右边界只往前走，不回头。