差分数组通过预处理将区间加减优化为两个单点操作：初始化diff[0]=arr[0], diff[i]=arr[i]−arr[i−1]（i>0）；对[l,r]加val执行diff[l]+=val、若r+1
差分数组的 C++ 实现核心逻辑
差分数组不是新容器，而是对原数组做一次预处理：用 diff[i] 记录 arr[i] 和 arr[i-1] 的差值。这样区间加减就退化成两个单点操作——这是它能优化的关键。
常见错误是直接在 diff 上模拟原数组更新，比如以为 diff[l] += val; diff[r] -= val; 就完事了，却忘了 r 的边界含义（闭区间还是开区间）和前缀和还原时的索引偏移。
- 初始化
diff[0] = arr[0]，其余diff[i] = arr[i] - arr[i-1]（i > 0） - 对
[l, r]区间加val：执行diff[l] += val;，若r+1 则 <code>diff[r+1] -= val; - 还原原数组：从左到右做前缀和，
arr[i] = diff[0] + ... + diff[i]，不能跳着算
C++ 中 vector<int></int> 差分数组的标准写法
用 std::vector 最稳妥，避免手动内存管理出错；注意大小要设为 n+1，方便处理 r+1 越界问题（多开一位，diff[n] 永远不参与还原，只用来承接减法）。
别用 int diff[n] 这种变长数组（C++ 标准不支持），也别用 new int[n] 后忘记 delete[]——现代 C++ 就该交给 vector 管。
立即学习“C++免费学习笔记（深入）”；
-
vector<int> diff(n + 1, 0);</int>—— 初始化全 0，安全 - 更新操作：
diff[l] += val;，if (r + 1 - 还原时用
for (int i = 1; i ，此时 <code>diff就变成了原数组
区间更新后单点查询为什么快？
单点查询本质就是求前缀和：查位置 i，只需把 diff[0] 到 diff[i] 全加起来。但如果你只查一次，没必要还原整个数组；可以边累加边停，时间复杂度 O(i)，最坏 O(n)。真正省时间的是「多次更新 + 多次单点查」场景。
容易踩的坑是误以为单点查一定是 O(1)——差分本身不提供 O(1) 单点查，它只是把 k 次区间更新的总代价从 O(k·n) 压到 O(k + n)。
- 如果只有 1 次更新 + 1 次查询，差分反而多此一举
- 如果更新频繁、查询稀疏，建议维护差分数组，查时再临时前缀和
- 如果查询极频繁（比如每更新一次就查一堆点），不如每次更新后直接维护一个前缀和数组
边界细节：l 和 r 是 0-indexed 还是 1-indexed？
取决于你读入的题意或接口约定。LeetCode 和多数算法题默认 0-indexed；但有些 OJ 或旧题描述用 1-indexed，这时你得把输入的 l、r 全部减 1 再进差分逻辑，否则 diff[l] 就会错位。
更隐蔽的坑是：当题目说「对区间 [l, r] 加 val」，这个区间是否包含端点？绝大多数情况是闭区间，即 l 和 r 都要被影响——所以差分操作必须是 diff[l] += val 和 diff[r+1] -= val，不是 diff[r]。
- 确认输入下标类型：打印一两个样例的
l、r看是否从 0 或 1 开始 - 统一在代码开头注释清楚：
// l, r are 0-indexed, inclusive - 测试用例至少覆盖
l == 0、r == n-1、l == r三种边界
差分数组真正的复杂点不在写法，而在“什么时候值得用”——它不解决所有区间问题，只对「大量区间加减 + 单点读取」这一特定模式有收益。很多人把它当成万能优化，结果在只需要一次查询的场景里徒增理解成本。
