差分

贡献者：有机物; addis

　　差分算法可以很快速的给一段区间 $[l, r]$ 加上一个数 $c$ 。

　　 一维差分

　　朴素的做法和前缀和类似，都是直接一个 for 循坏给区间中的每个数都加 $c$ ，朴素做法的时间复杂度为 $O (n \times m)$ ， $n$ 为序列大小， $m$ 为询问次数。

　　差分做法是，构造一个差分数组 $b$ ，使得 $b_{i} = a_{i} - a_{i - 1}$ ， $(i \geq 2)$ ，特殊的，规定 $b_{1} = a_{1}$ 。因此 $a$ 数组就是 $b$ 数组的前缀和， $b$ 数组就称是 $a$ 数组的差分数组。 ${\begin{cases} b_{1} = a_{1} \\ b_{2} = a_{2} - a_{1} \\ b_{3} = a_{3} - a_{2} \\ \dots \\ b_{i} = a_{i} - a_{i - 1} \end{cases},$

\begin{matrix} (1) & \sum_{k = 1}^{i} b_{k} = \sum_{k = 1}^{i} a_{k} - \sum_{k = 1}^{i - 1} a_{k} = a_{i}, \end{matrix}

所以，对

b

数组求前缀和就等于

a

数组。

　　若要对 $[l, r]$ 中的每个数加 $c$ ，对应在 $a$ 数组就是 $c \sum_{i = l}^{r} a_{i}$ 。可以直接在 $b$ 数组上对 $b_{l}$ 这个位置加 $c$ ，那么在求 $a$ 数组时， $a_{l}$ 、 $a_{l + 1}$ 、 $a_{l + 2}$ $\dots$ $a_{n}$ 都会加上 $c$ 。因为 $a$ 数组就是 $b$ 数组的前缀和。

　　例子：假设要对 $[1, n]$ 每个数都加 $c$ ，那么只需要将 $b_{1}$ 加 $c$ 即可。可见 $a_{1 . . . n}$ 都加了 $c$ 。

　　 ${\begin{cases} a_{1} = a_{0} + b_{1} \\ a_{2} = a_{1} + b_{2} \\ \dots \\ a_{n} = a_{n - 1} + b_{n} \end{cases}$

　　因为只需要在 $[l, r]$ 中的每个数加 $c$ ， $a_{r + 1 . . . n}$ 这些数是不需要加的，我们只需要对应在 $b_{r + 1}$ 减去 $c$ 就行了。对应在 $a$ 数组就是 $a_{r + 1. . n}$ 这些数没有任何变化。

const int N = 1e5 + 10;
int n, m, a[N], b[N];

int main() 
{
    cin >> n >> m;  
    for (int i = 1; i <= n; i ++ ) cin >> a[i];
    for (int i = 1; i <= n; i ++ ) b[i] = a[i] - a[i - 1]; // 构造差分数组

    while (m -- ) // m 次询问
    {
        int l, r, c;
        cin >> l >> r >> c;
        b[l] += c, b[r + 1] -= c;   // O(1) 计算
    }
    
    for (int i = 1; i <= n; i ++ ) 
    {
        a[i] = a[i - 1] + b[i]; // 求一遍前缀和
        cout << a[i] << ' ';   
    }
    
    return 0;
}

　　另外一种构造方式：

void insert(int l, int r, int c)
{
    b[l] += c;
    b[r + 1] -= c;
}

int main()
{
    cin >> n >> m;
    for (int i = 1; i <= n; i ++ ) 
    {
        cin >> a[i];
        insert(i, i, a[i]);
    }
    
    while (m -- )
    {
        int l, r, c;
        cin >> l >> r >> c;
        insert(l, r, c);
    }
    
    for (int i = 1; i <= n; i ++ ) 
    {
        a[i] = a[i - 1] + b[i];
        cout << a[i] << ' ';
    }
    
    return 0;
}

　　上面两种写法是等价的。

　　下面介绍二维差分：

　　二维差分是将一个矩阵内部以 $(x_{1}, y_{1})$ 左上角、 $(x_{2}, y_{2})$ 为右下角的子矩阵内部的每个元素都加 $c$ 。

　　朴素做法类似于一维差分，时间复杂度为 $O (q \times n^{2})$ ， $q$ 为询问次数， $n^{2}$ 为子矩阵大小。

　　二维差分也同样是构造一个二维差分数组，使得二维数组 $a$ 是 $b$ 数组的二维前缀和。怎么构造差分数组可以不用考虑，只需要考虑核心操作，然后对矩阵中的每个数做一遍核心操作即可构造好 $b$ 数组。可以直接在 $b$ 数组上进行如下几个操作：

$b_{x_{1}, y_{1}}$ 加 $c$
$b_{x_{1}, y_{2} + 1}$ 减 $c$
$b_{x_{2} + 1, y 1}$ 减 $c$
$b_{x_{2} + 1, y_{2} + 1}$ 加 $c$

　　执行完以上 $4$ 个操作，再对 $b$ 数组求一遍前缀和。就可以得到期望答案。

　　具体来讲：(都会求前缀和)执行完操作 $1$ 后，以 $x_{1}, y_{1}$ 为左上角的矩阵都被加了 $c$ 。执行完操作 $2$ 后，以 $x_{1}, y_{2} + 1$ 为左上角的矩阵都被减了 $c$ 。执行完操作 $3$ 后，以 $x_{2} + 1, y 1$ 为左上角的矩阵都被减了 $c$ 。执行完操作 $4$ 后，以 $x_{2} + 1, y_{2} + 1$ 为左上角的矩阵都被加了 $c$ 。

　　二维差分还是比较抽象，可以根据几张图来理解：

图 1：操作

1

图 2：操作

2

图 3：操作

3

、

4

const int N = 1100;
int n, m, q, a[N][N], b[N][N];

void insert(int x1, int y1, int x2, int y2, int c)
{
    b[x1][y1] += c;
    b[x1][y2 + 1] -= c;
    b[x2 + 1][y1] -= c;
    b[x2 + 1][y2 + 1] += c;
}

int main()
{
    cin >> n >> m >> q;
    for (int i = 1; i <= n; i ++ ) 
        for (int j = 1; j <= m; j ++ )
        {
            cin >> a[i][j];
            insert(i, j, i, j, a[i][j]);   // 构造差分数组 b
        }
        
    while (q -- )
    {
        int x1, y1, x2, y2, c;
        cin >> x1 >> y1 >> x2 >> y2 >> c;
        insert(x1, y1, x2, y2, c);
    }
    
    for (int i = 1; i <= n; i ++ ) 
    {
        for (int j = 1; j <= m; j ++ )
        {
            // 求 a 数组，就是求 b 的二维前缀和
            a[i][j] = a[i - 1][j] + a[i][j - 1] 
                    - a[i - 1][j - 1] + b[i][j];    
            cout << a[i][j] << ' ';
        }
        cout << endl;
    }

    return 0;
}

致读者：小时百科一直以来坚持所有内容免费无广告，这导致我们处于严重的亏损状态。长此以往很可能会最终导致我们不得不选择大量广告以及内容付费等。因此，我们请求广大读者热心打赏 ，使网站得以健康发展。如果看到这条信息的每位读者能慷慨打赏 20 元，我们一周就能脱离亏损，并在接下来的一年里向所有读者继续免费提供优质内容。但遗憾的是只有不到 1% 的读者愿意捐款，他们的付出帮助了 99% 的读者免费获取知识，我们在此表示感谢。