差分学习记录

Leo_29 · 2026-01-23 19:41:28 · 个人记录

差分介绍

差分是一种与前缀和相对的策略，是前缀和的逆运算．相较于给定某一序列求它的差分，竞赛中更为常见的情景是，通过维护差分序列的信息，实现多次区间修改．在区间修改结束后，可以通过前缀和恢复原序列的信息，实现对原序列的查询．注意修改操作一定要在查询操作之前．—— OI Wiki 对差分的介绍。

我们先来看一道简单题目来了解一下差分这种技巧。

引入例题

我们有一个长度为 n 的序列，初始所有值都为 0。

现在，我们有 m 个操作，第 i 个操作给出 x_i 与 y_i，要求我们将序列 [x_i, y_i] 部分全部加上一。

输出经过操作后的序列。

输入格式如下：

第一行两个数，为 n，m。

接下来 m 行，第 i 行有两个数 x_i 与 y_i。

这题乍一看是暴力对吧？我们每次操作都直接将区域中的每个数加一，就可以解决此问题了。时间复杂度约为 O(m \times n)。

但是，如果 n，m 的范围都很大，我们该如何处理呢？

这里，我们就要引入今天的技巧——差分。

我们给出一个样例：

暴力操作是这样的：

原序列为 0 0 0 0 0 0。
经过第一次操作，序列变为了 0 1 1 1 1 0。
经过第二次操作，序列变成了 1 2 2 2 1 0。
经过第三次操作，序列变成了 1 2 3 3 2 1。
操作完毕，输出现在的序列。

很明显，暴力操作每次都要更新一次序列，非常麻烦。

那么，我们来看一下差分操作的步骤：

引入一个新数组 b，初始全部值为 0。
第一次操作，b 数组变为 0 1 0 0 0 -1。
第二次操作，b 数组变为 1 1 0 0 -1 -1。
第三次操作，b 数组变为 1 1 1 0 -1 -1 (-1)。
然后，我们引入变量 c，初始等于 0。遍历数组 b，对于下标 i 执行 c \rightarrow c + b_i。然后，我们记 a_i = c。
操作完毕，输出数组 a。

我们的操作过程是：

1. c = 1
2. c = 2
3. c = 3
4. c = 3
5. c = 2
6. c = 1

哎？为什么这样操作，得出的也是正确结果呢？像这样操作，我们的时间复杂度就变为了 O(n + m)，比原来快多了。

::::success[正确代码]

#include <bits/stdc++.h>
using namespace std;
int n, m;
int flag[1000010];
int main()
{
    cin >> n >> m;
    for(int i = 1, x, y;i <= m;i ++)
    {
        cin >> x >> y;
        flag[x] ++, flag[y + 1] --;//打下标记 
    }
    int c = 0;
    for(int i = 1;i <= n;i ++)
    {
        c += flag[i];//增加标签大小 
        cout << c << " ";//现在记录的总标记大小即为此位的答案 
    }
    return 0;
}

::::

这里，我们就要正式开始介绍差分算法了（只是简单的解释）。当我们要进行一次区间加减操作时，设操作的区间为 [x, y]，我们将标记数组的下标 x 的值加一，下标 y + 1 的值减一。

这样，当我们需要求最终的总和时，变量从下标 x 开始加一，到了下标 y + 1 又减一，在此过程中完成了区间增加的操作。

简单来说，就是我们在完成标记后，从左往右扫描这个标记数组，记录当前经过的标记之和。这个和就是对应那个数的值。

以上部分是自己的思想，可能描述的不太好，大家自行理解，请谅解。

习题与解析

P3397 地毯

很明显是二维的差分，其实我们把刚才的例题代码改成二维的即可解决这道题目了（看成有 n 个数组，有 n 个标记数组就行了）。

::::success[正确代码]

#include <bits/stdc++.h>
using namespace std;
int n, m;
int a[1010][1010], fg[1010][1010];
int main()
{
    cin >> n >> m;
    for(int i = 1, xa, ya, xb, yb;i <= m;i ++)
    {
        cin >> xa >> ya >> xb >> yb;
        for(int j = xa;j <= xb;j ++)
            fg[j][ya] ++, fg[j][yb + 1] --;
    }
    for(int i = 1;i <= n;i ++)
    {
        int c = 0;
        for(int j = 1;j <= n;j ++)
            c += fg[i][j], a[i][j] = c;     
    }

    for(int i = 1;i <= n;i ++)
    {
        for(int j = 1;j <= n;j ++)
            cout << a[i][j] << " ";
        cout << endl;
    }
    return 0;
}

::::

P3406 海底高铁

这题如果想到了是差分那就很简单了，但是难的就是这个思维过程。

首先，由于从城市 x 到城市 y（x < y）必须这么走：x \rightarrow x + 1 \rightarrow x + 2 \rightarrow \dots \rightarrow y。那么，我们每次得到两个城市的的差分标记就可以打出来了。

在打完差分标记后，我们就可以求出会经过每段道路的次数了。在求出这个次数后，我们就可以判断是每次都买票好还是买卡好了。

这样，我们就可以求出最终的答案了。

注意要开 long long。

::::success[正确代码]

#include <bits/stdc++.h>
using namespace std;
int n, m, p1, p2;
long long ans = 0;
int flag[100010];
int main()
{
    cin >> n >> m;
    cin >> p1;
    for(int i = 2;i <= m;i ++)
    {
        cin >> p2;
        if(p1 > p2)//差分部分，注意判断两个城市的先后顺序 
        {
            flag[p2] ++;
            flag[p1] --;
        }
        else
        {
            flag[p1] ++;
            flag[p2] --;
        }
        p1 = p2;//再继承一下 
    }
    long long k = 0;
    for(int i = 1, a, b, c;i < n;i ++)
    {
        cin >> a >> b >> c;
        k += flag[i];//差分求到每段路的次数 
        ans += min(k * a, c + k * b);//判断那个方式合算 
    }

    cout << ans << endl;
    return 0;
}

::::