差分算法详解：从一维到二维的优化技巧

差分算法详解：从一维到二维的优化技巧

引用

CSDN

1.

https://blog.csdn.net/yuanManGan/article/details/145528752

差分算法是算法竞赛和实际开发中常用的一种优化技术，主要用于对数组区间进行快速的加减操作。本文将从一维差分和二维差分两个方面，通过具体的题目和代码示例，帮助读者深入理解差分算法的核心思想和应用场景。

差分算法简介

差分算法的核心思想是预处理，可以在暴力枚举的过程中，快速给出查询的结果，从而优化时间复杂度。这是一种经典的用空间替换时间的做法。

学完差分之后，大家会发现，前缀和与差分是一对互逆的运算。差分主要是用于对一个区间整体加或者减去同一个数这类问题。

一维差分

题目理解

给了一个长度为n的数组，要求对数组 l 到 r 区间进行加上 k 的处理进行m次，然后输出数组的所有元素。

思路讲解

暴力解法

要求对那个区间进行操作我们就一次for循环加上k就行了，但时间复杂度为m*n(1e5 * 1e5)显然会超时，这时我们就引出了差分数组。

差分

我们依旧像前缀和一样，创建一个差分数组，这里存储的不再是前缀和，而是这一位元素减去上一位元素的值。

这就是一个差分数组，但我们要解决题目，这个差分数组有什么用呢？别急，我们先对原数组一个区间加上一个数，发现差分数组只改变了两个数，时间复杂度就从O(n)变成了O(1)了。

我们如果要在x~y区间加上k，就等价于a[x] += k , a[ y + 1] -= k.只需要改变这两个数就可以解决问题了。

心急的朋友这时又要问了，那我怎么还原原数组呢，我们仅需要对差分数组求前缀和就解决问题了，是不是很奇妙呢，所以说差分与前缀和互为逆运算。

代码实现

#include<iostream>
using namespace std;
typedef long long LL;
const int N = 1e5 + 10;
int n, m;
//差分数组
LL f[N];
int main()
{
    cin >> n >> m;
    //预处理
    for (int i = 1; i <= n; i++)
    {
        LL x; cin >> x;
        f[i] += x;
        f[i + 1] -= x;
    }
    //进行m次操作
    while (m--)
    {
        int l, r, k; cin >> l >> r >> k;
        f[l] -= k, f[r + 1] += k;
    }
    //对差分数组求前缀和还原
    for (int i = 1; i <= n; i++)
    {
        f[i] += f[i - 1];
        cout << f[i] << " ";
    }
    return 0;
}

二维差分

直接上题目：

题目理解

给了个二维数组，要求对以(x1, y1)为左上角,(x2,y2)为右下角的子矩阵的每个元素都加上k，进行q次操作，最后输出数组

思路讲解

暴力解法

叫你加你就加，老老实实最后换来时间复杂度：O(n * m * q) = 1e4 * 1e4 * 1e5。时间复杂度都上天了。

二维差分

差分数组的初始化先别忙着讲，先解决对以(x1, y1)为左上角,(x2,y2)为右下角的子矩阵的每个元素都加上k，这个问题，然后x1 = x2，y1 = y2, k = x，不就解决了差分数组初始化的问题了吗？

这是原数组，我们像实现如图的功能 。

我们从一维数组了解到，对差分数组求前缀和能得到原始数组，那我们不妨假设一个差分数组对任意位置加上一个k试试

然后我们对这个数组求前缀和，发现以x1，y1为左上角的矩阵的前缀和都受到了影响，都加上了k。

但我们只需但我们只需要对 以(x1, y1)为左上角,(x2,y2)为右下角的子矩阵的每个元素都加上k，我们再把边上的减去就成了：

发现就差一点就能完成任务了，最后将x2 + 1， y2 + 1位置加上k就大功告成了！

代码展示

#include <iostream>
using namespace std;
typedef long long LL;
const int N = 1e4 + 10;
//差分数组
LL f[N][N];
int n, m, q;
//添加k操作
void insert(LL x1, LL y1, LL x2, LL y2, LL k)
{
    f[x1][y1] += k; f[x2 + 1][y2 + 1] += k;
    f[x1][y2 + 1] -= k; f[x2 + 1][y1] -= k;
}
int main()
{
    cin >> n >> m >> q;
    //预处理差分数组
    for (int i = 1; i <= n; i++)
    {
        for (int j = 1; j <= m; j++)
        {
            LL x; cin >> x;
            insert(i, j, i, j, x);
        }
    }
    //进行q次操作
    while (q--)
    {
        int x1, y1, x2, y2, k;
        cin >> x1 >> y1 >> x2 >> y2 >> k;
        insert(x1, y1, x2, y2, k);
    }
    //前缀和差分数组还原原数组
    for (int i = 1; i <= n; i++)
    {
        for (int j = 1; j <= m; j++)
        {
            f[i][j] += f[i - 1][j] + f[i][j - 1] - f[i - 1][j - 1];
            cout << f[i][j] << " ";
        }
        cout << endl;
    }
}

练习题

一维差分

• 海底高铁

二维差分

• 地毯

答案

海底高铁

#include<iostream>
using namespace std;
typedef long long LL;
const int N = 1e5 + 10;
int n, m;
LL f[N];
int main()
{
    cin >> n >> m;
    int x; cin >> x;
    for (int i = 2; i <= m; i++)
    {
        int y; cin >> y;
        if (x > y) f[x]--, f[y]++;
        else f[y]--, f[x]++;
        x = y;
    }
    //还原原数组
    for (int i = 1; i <= n; i++) f[i] += f[i - 1];
    LL ret = 0;
    for (int i = 1; i < n; i++)
    {
        int a, b, c; cin >> a >> b >> c;
        ret += min(a * f[i], c + b * f[i]);
    }
    cout << ret << endl;
    return 0;
}

地毯

#include<iostream>
using namespace std;
const int N = 1010;
int n, m;
int f[N][N];
int main()
{
    cin >> n >> m;
    while (m--)
    {
        int x1, y1, x2, y2; cin >> x1 >> y1 >> x2 >> y2;
        f[x1][y1]++; f[x2 + 1][y1]--; 
        f[x1][y2 + 1]--; f[x2 + 1][y2 + 1]++;
    }
    //还原
    for (int i = 1; i <= n; i++)
    {
        for (int j = 1; j <= n; j++)
        {
            f[i][j] += f[i - 1][j] + f[i][j - 1] - f[i - 1][j - 1];
            cout << f[i][j] << " ";
        }
        cout << endl;
    }
    return 0;
}