1. 引言
想象你在竞赛中遇到一道题，要求你“对数组进行 $10^6$ 次区间加法操作”，并最后输出数组。如果你直接暴力遍历每个元素修改，时间复杂度是 $O(nq)$（$q$ 为操作次数），必然超时。而学会差分数组后，你可以将时间复杂度优化到 $O(q + n)$——这就是本课的核心！
2. 核心概念讲解
什么是差分数组？
差分数组是一种高效处理批量区间修改的数据结构。定义：
设原数组为
a[1..n]，差分数组d[1..n+1]满足d[i] = a[i] - a[i-1]（其中a[0]=0）。区间加法
[l, r] += val只需：
d[l] += val;
d[r+1] -= val; // 如果 r+1 <= n
- 查询单点
a[i]时，只需计算前缀和sum_{k=1}^i d[k]。
图示说明：
| 原数组 | [1,3] += 5 |
|——-|———–|
| 初始值 | [0,0,0,0] |
| 差分更新 | [5,0,0,-5] |
| 还原数组 | [5,5,5,0] |
3. C++代码示例
以下是一个用差分数组实现区间加法和单点查询的完整示例（支持 $10^6$ 级数据）：
#include <bits/stdc++.h>
using namespace std;
const int N = 1e6 + 5; // 根据题目数据范围调整！
int diff[N]; // 差分数组
int prefix[N]; // 前缀和数组，用于O(1)查询
void range_add(int l, int r, int val) {
if (l >= 1 && r < N) { // 防止越界
diff[l] += val;
diff[r + 1] -= val;
}
}
// 预处理前缀和数组（仅需在查询前调用一次）
void build_prefix() {
prefix[0] = 0;
for (int i = 1; i < N; ++i)
prefix[i] = prefix[i - 1] + diff[i];
}
int query(int x) {
return prefix[x]; // O(1)查询
}
int main() {
int n, q;
cin >> n >> q;
// 初始化差分数组和前缀和
memset(diff, 0, sizeof(diff));
build_prefix();
while (q--) {
int op, l, r, x;
cin >> op;
if (op == 1) { // 区间加
cin >> l >> r >> x;
range_add(l, r, x);
// 注意：若需实时查询，必须重新build_prefix()
} else { // 单点查询
cin >> l;
cout << query(l) << '\n';
}
}
return 0;
}
注释：
N的取值：务必根据题目输入范围设置，避免越界。range_add：通过差分标记边界，无需逐个修改元素。build_prefix：预处理前缀和数组，使后续查询均为 $O(1)$。实时性：若操作和查询交替频繁，可每 $k$ 次操作后统一调用
build_prefix()，减少重复计算。
4. 算法分析
时间复杂度：
区间更新：$O(1)$
单点查询：预处理后 $O(1)$，未预处理则每次 $O(n)$（见下方误区）
空间复杂度：$O(N)$
适用场景：
高频区间修改 + 低频单点查询
数据规模大（如 $n=1e6, q=1e5$）
局限性：
不支持区间查询（需用线段树或前缀和数组）
若查询频率高，需权衡预处理开销
5. 常见误区
- 越界问题：
- 当
r = n-1时，diff[r+1]可能越界，需特判。
- 前缀和更新时机：
若每次查询都调用
accumulate(diff, diff+l)，时间复杂度退化为 $O(nq)$。正确做法：预处理
prefix数组或使用树状数组（如需动态更新）。
- 负数下标：
- 某些语言（如C++）中
diff[0]是合法内存，但逻辑上a[0]=0，需确保不访问diff[0]。
6. 经典例题
题目1：洛谷 P2708 数列 https://www.luogu.com.cn/problem/P2708
题意：给定初始数组，支持区间加、区间求和操作。
思路：
用差分数组处理区间加法。
维护前缀和数组
prefix_sum，使得区间和sum[l..r] = prefix_sum[r] - prefix_sum[l-1]。
- 关键代码：
void add_range(int l, int r, int val) {
diff[l] += val;
if (r + 1 < N) diff[r + 1] -= val;
}
// 每次修改后更新前缀和数组
for (int i = 1; i < N; ++i)
prefix_sum[i] = prefix_sum[i - 1] + diff[i];
题目2：CF1439C 数组操作 https://codeforces.com/contest/1439/problem/C
题意：多次对数组子区间加固定值，最后输出整个数组。
思路：
对所有区间操作先记录在差分数组。
最后遍历差分数组还原数组（时间复杂度 $O(n+q)$）。
- 完整代码：
int main() {
int n, m;
cin >> n >> m;
memset(diff, 0, sizeof(diff));
while (m--) {
int l, r, k;
cin >> l >> r >> k;
range_add(l, r, k);
}
// 输出结果
for (int i = 1; i <= n; ++i)
cout << prefix[i] << ' ';
return 0;
}
7. 推荐练习
洛谷 P3368 历史最值 （难度★☆）：结合单调栈模拟历史最值。
CF1096F 区间赋值 （难度★★★）：差分数组+懒惰标记的进阶应用。
8. 小结
核心要点：
差分数组的核心思想是“批量修改，延迟计算”。
预处理前缀和数组可实现 $O(1)$ 单点查询。
根据题目需求选择是否实时更新前缀和。
下期我们将学习如何用线段树应对更复杂的区间操作！
**
🌐 友情链接： 欢迎访问我们的国际版站点 noiquest.com - 全球算法竞赛资源分享平台
💬 互动时间：你在学习过程中有什么疑问？在评论区告诉我，我会选择有代表性的问题详细解答！
📚 相关推荐：