差分算法

差分算法

1. 简介与概述、功能介绍

差分算法是一种与前缀和算法紧密相关的算法，主要用于高效处理区间修改问题。通过构造差分数组，能够将对数组某一区间的元素进行统一修改的操作，转化为对差分数组中两个端点的修改，从而将区间修改的时间复杂度从 $O(n)$ 降低到 $O(1)$。在完成所有修改操作后，再通过差分数组还原出原数组，即可得到修改后的结果。

2. 适用场景

• 区间修改问题：当需要对数组的多个区间进行频繁的统一修改（如区间内所有元素加上或减去一个固定值），且最终只需要查询修改后的数组整体情况时，差分算法能显著提高效率。
• 离线区间修改问题：即所有的修改操作在查询之前一次性给出，不需要实时响应查询结果的场景。

3. 算法原理详解

差分数组的构造

对于一个长度为 $n$ 的数组 $arr$，其差分数组 $dif$ 的定义如下： $dif[0] = arr[0]$ $dif[i] = arr[i] - arr[i - 1]$，其中 $i > 0$

区间修改操作

若要对数组 $arr$ 的区间 $[l, r]$ 内的所有元素加上一个值 $x$，只需要对差分数组 $dif$ 进行如下操作： $dif[l] += x$ $dif[r + 1] -= x$（前提是 $r + 1 < n$）

这样做的原理是，差分数组记录了原数组相邻元素的差值，对 $dif[l]$ 加上 $x$ 后，从 $l$ 位置开始，后续元素在还原时都会比原来多 $x$；而对 $dif[r + 1]$ 减去 $x$，则保证了从 $r + 1$ 位置开始，后续元素不受这次区间修改的影响。

还原原数组

完成所有区间修改操作后，通过差分数组还原出原数组，公式为： $arr[0] = dif[0]$ $arr[i] = arr[i - 1] + dif[i]$，其中 $i > 0$

4. 经典例题及代码实现

题面：给定一个长度为 $n$ 的整数数组 $arr$，以及 $m$ 个区间修改操作，每个操作包含三个整数 $l$、$r$ 和 $x$，表示将数组中区间 $[l, r]$ 内的所有元素加上 $x$。输出经过所有修改操作后的数组。 输入格式： 第一行包含两个整数 $n$ 和 $m$，分别表示数组的长度和修改操作的数量。 第二行包含 $n$ 个整数，表示数组 $arr$。 接下来的 $m$ 行，每行包含三个整数 $l$、$r$ 和 $x$，表示一个区间修改操作。 输出格式： 输出经过所有修改操作后的数组，元素之间用空格分隔。 输入样例：

5 3
1 2 3 4 5
0 2 1
1 3 2
2 4 3

输出样例：

2 5 7 9 8

#include <iostream>
using namespace std;
 
const int MAXN = 100005;
int arr[MAXN];
int dif[MAXN];
 
// 构造差分数组
void cal_dif(int n) {
    dif[0] = arr[0];
    for (int i = 1; i < n; i++) {
        dif[i] = arr[i] - arr[i - 1];
    }
}
 
// 区间修改操作
void upd(int l, int r, int x) {
    dif[l] += x;
    if (r + 1 < MAXN) {
        dif[r + 1] -= x;
    }
}
 
// 还原原数组
void rec(int n) {
    arr[0] = dif[0];
    for (int i = 1; i < n; i++) {
        arr[i] = arr[i - 1] + dif[i];
    }
}
 
int main() {
    int n, m;
    // 读入数组长度和修改操作数量
    cin >> n >> m;
    // 读入数组元素
    for (int i = 0; i < n; i++) cin >> arr[i];
    // 构造差分数组
    cal_dif(n);
    for (int i = 0; i < m; i++) {
        int l, r, x;
        // 读入区间修改操作
        cin >> l >> r >> x;
        // 进行区间修改
        upd(l, r, x);
    }
    // 还原原数组
    rec(n);
    // 输出修改后的数组
    for (int i = 0; i < n; i++) {
        cout << arr[i];
        if (i < n - 1) cout << " ";
    }
    cout << endl;
    return 0;
}

5. 总结

• 优点：差分算法将区间修改的时间复杂度从 $O(n)$ 降低到 $O(1)$，在处理大量区间修改操作时效率极高。
• 缺点：需要额外的 $O(n)$ 空间来存储差分数组，并且需要进行差分数组的构造和原数组的还原操作。
• 适用情况：适用于需要频繁进行区间修改，且最终只需要查询数组整体情况的场景。在实际应用中，要根据具体问题合理运用差分算法，以提高算法的效率。

例题