C++ 差分教程

差分是一种常用的数学方法，用于高效处理区间修改问题。在算法竞赛和实际应用中经常会用到。下面我将详细介绍差分的概念、原理和使用方法。

1. 什么是差分？

差分是一种数据结构，用于高效处理对数组的区间修改操作。
假设有一个数组 a = [a₁, a₂, a₃, ..., aₙ]，我们可以构造一个差分数组 d，使得：

• d[1] = a[1]
• d[i] = a[i] - a[i-1]（i ≥ 2）

简单来说，差分数组记录了原数组中每个元素与前一个元素的差值。

2. 差分数组的作用

差分数组的主要作用是：将区间修改操作转化为单点修改操作，从而将时间复杂度从 O(n) 降为 O(1)。

例如，要对原数组 a 的区间 [l, r] 内的所有元素加上一个值 k，只需要在差分数组 d 上进行以下操作：

• d[l] += k
• d[r+1] -= k（如果 r+1 ≤ n）

最后，通过差分数组还原出原数组时，区间 [l, r] 内的元素都会被加上 k，而其他元素不受影响。

3. 如何构造差分数组？

假设原数组为 a，差分数组为 d，构造方法如下：

#include <iostream>
#include <vector>
using namespace std; // 使用标准命名空间，避免重复写std::

int main() {
    // 原数组（下标从1开始）
    vector<int> a = {0, 3, 5, 7, 2, 9}; // 注意：a[0] 不使用，从 a[1] 开始
    int n = a.size() - 1; // 数组长度
    
    // 构造差分数组
    vector<int> d(n + 2, 0); // 差分数组长度为 n+2，避免越界
    for (int i = 1; i <= n; i++) {
        d[i] = a[i] - a[i-1];
    }
    
    // 输出差分数组
    cout << "差分数组 d: ";
    for (int i = 1; i <= n; i++) {
        cout << d[i] << " ";
    }
    cout << endl;
    
    return 0;
}

输出结果：

差分数组 d: 3 2 2 -5 7 

4. 如何进行区间修改？

假设要对原数组 a 的区间 [2, 4] 内的所有元素加上 3，只需修改差分数组：

#include <iostream>
#include <vector>
using namespace std;

int main() {
    // 原数组
    vector<int> a = {0, 3, 5, 7, 2, 9};
    int n = a.size() - 1;
    
    // 构造差分数组
    vector<int> d(n + 2, 0);
    for (int i = 1; i <= n; i++) {
        d[i] = a[i] - a[i-1];
    }
    
    // 区间 [2, 4] 加 3
    int l = 2, r = 4, k = 3;
    d[l] += k;
    if (r + 1 <= n) d[r+1] -= k;
    
    // 通过差分数组还原原数组
    vector<int> new_a(n + 1, 0);
    new_a[1] = d[1];
    for (int i = 2; i <= n; i++) {
        new_a[i] = new_a[i-1] + d[i];
    }
    
    // 输出修改后的原数组
    cout << "修改后的原数组: ";
    for (int i = 1; i <= n; i++) {
        cout << new_a[i] << " ";
    }
    cout << endl;
    
    return 0;
}

输出结果：

修改后的原数组: 3 8 10 5 9 

5. 差分的应用场景

差分常用于处理频繁的区间修改问题，例如：

• 多次对数组的不同区间进行加法操作，最后查询数组的某个位置或整体状态。
• 线段树、树状数组等高级数据结构的基础。
• 游戏开发中的技能范围伤害计算。

6. 注意事项

1. 数组下标：上述示例中，数组下标从 1 开始，这样更符合差分的数学定义。
2. 边界处理：修改差分数组时，要注意 r+1 是否越界。
3. 还原原数组：通过差分数组还原原数组时，需使用前缀和公式：a[i] = a[i-1] + d[i]。

7. 练习题

1. 给定数组 a = [1, 2, 3, 4, 5]，对区间 [2, 4] 加 2，区间 [3, 5] 加 3，最后输出修改后的数组。
2. 设计一个程序，支持多次区间加法操作，并能快速查询任意位置的值。

总结

差分是一种非常实用的预处理技巧，通过将区间修改转化为单点修改，大大提高了处理效率。掌握差分后，很多区间修改问题都能迎刃而解。