【模版】差分

问题引入：洛谷P2367

班上一共n个学生，语文老师需要对成绩进行p次修改，每次修改需要给第x个学生到第y个学生每个人增加z分，语文老师想知道修改成绩后的最低分。

对于 $40\%$ 的数据，有 $n \le 10^3$。

对于 $60\%$ 的数据，有 $n \le 10^4$。

对于 $80\%$ 的数据，有 $n \le 10^5$。

对于 $100\%$ 的数据，有 $n \le 5\times 10^6$，$p \le n$，学生初始成绩 $ \le 100$，$z \le 100$。

分析：直接模拟修改的时间复杂度为O（n²），肯定无法通过本题

一维差分的定义：对于这个原数组 a[ ] = {a1，a2，a3，···，an}，我们构造出这样一个数组 B[ ] = {b1，b2，b3，···，bn}，使得 ai = b1 + b2 + ··· + bi，那么b[ ] 就称为 a[ ] 的差分，a[ ] 称为 b[ ] 的前缀和。其中b1 = a1，b[i] = a[i] - a[i-1] （2<=i<=n)，可以发现，差分与前缀和是一组逆运算。

 如何利用差分数组对区间进行修改呢？为什么利用差分数组能提升修改的效率呢？

• 1.区间修改，时间复杂度为 O（1）

​ 现在要将原数组 a[ ] 区间【L，R】上的每个数都加上一个 c，如下图所示：

• 第一个受到影响的差分数组中的元素为 bL]，所以 b[L] += c ，对于 a[L] 后面的数都会受到 B[L] 的影响加上 c。
• 最后一个受影响的差分数组中的元素b[R]，为了保证不影响到 R 后面的元素，所以我们需要 b[R + 1] -= c。

也就是说，对于 a[x] = b[1] + b[2] + ···+ b[x]，利用差分数组能够精确地实现只修改指定区间内元素的目的，而不会修改区间外的a[ ] 的值，也就是：

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

(1) 1 ≤ x < L, 前缀和 a[x] 不变。
(2) L ≤ x ≤ R, 前缀和 a[x] 加上了 c 。
(3) R < x ≤ N, 前缀和 a[x] 不变，因为被 b[R + 1] 中的c抵消了。
这样一来，就不必每次都对区间内所有的数进行处理，只需要修改区间【L，R】的两个端点 b[ ] 的值即可，复杂度是 O(1) 的。

本题AC代码：

#include<iostream>
#include<cstdio>
using namespace std;
#define MAXN 5000010
int n,m,x,y,z,a[MAXN],b[MAXN];
int main() {
    cin >>n>>m;
    for (int i=1;i<=n;i++) {
        cin >>a[i];
        b[i] = a[i]-a[i-1];   //求差分数组，也可以insert(i,i,a[i])
    }
    for (int i=1;i<=n;i++) {
        cin >>x>>y>>z;
        b[x]+=z;
        b[y+1]-=z;       //修改操作
    }
    int min = 101;
    for (int i=1;i<=n;i++) {
        b[i] += b[i-1];   //求前缀和
        if(b[i]<min) min = b[i];
    }
    cout << min;
    
    return 0;
}

差分的局限性：我们可以注意到，利用差分数组 b[] 可以将原来O ( n ) 的区间修改，降为O ( 1 ) 的端点修改，从而提高了修改操作的效率。

但是，对于一次的查询操作，我们必须计算前缀和 b[1] + b[2] + ··· + b[x]才能将原数组 a[x] 求出，计算量是 O ( n )的，即一次查询的复杂度是 O ( n ) 的。也就是说，如果查询操作发生多次，例如 m 次修改，k 次查询，且修改和查询的顺序是随机的，即可能边修改边查询。此时总复杂度为：m 次修改复杂度 O ( m )，k次查询复杂度 O ( k n )，即 o ( m + k n ) 。还不如直接暴力来的快 O ( m n + k )。

可以看出，尽管差分数组对于 ”区间修改“很高效，但是对于”单点查询“来说略显吃力。此时有专门的数据结构来解决这一类问题：树状数组和线段树。

 二维差分：

有了一维差分的认识后，我们容易就能拓展到二维差分。一维是线性的，一段区间【L，R】有两个端点；二维是一个矩阵，一块区间由四个端点所围成。

问题描述: 在 n × n 的格子上有 m 个地毯。给出这些地毯的信息，问每个点被多少地毯覆盖。

输入： 第一行是两个整数n， m。接下来 m 行，每行 2 个坐标(x1, y1) 和 (x2, y2 )，代表一块地毯，左上角是 (x1, y1)，右下角是(x2, y2)。

输出：输出n行，每行n个正整数。第i行第j列的正整数表示(i, j)这个格式被多少地毯覆盖。

同前面一样考虑朴素算法，每次修改时间复杂度为O（n²），共 m 次，所以时间复杂度为O（m+n²），肯定超时

(1)二维差分的定义

 在一维差分中，原数组a[ ]是从第1个b[1]开始的差分数组 b[ ]的前缀和：a[x]= b[1] + b[2] + ··· + b[x]。
 在二维差分中，a[ ][ ]是差分数组b[ ][ ]的前缀和，即将原点坐标(1,1)和坐标(i,j)围成的矩阵中，所有的b[ ][ ]相加等于a[ i ][ j ]。我们可以把每个b[][]看成一个小格；在坐标（1，1）和（i，j）所围成的范围内，所有小格子加起来的总面积，等于 a[i][j]。如下图中，每个格子的面积是一个 b[ ][ ]，例如阴影格子是b[ i ][ j ]，它由4个坐标点组成：( i , j )、( i − 1 , j )、( i , j − 1 ) 、( i − 1 , j − 1 ) 。坐标点(i, j)的值是 a[ i ][ j ]，它等于坐标(1，1)和(i，j)所围成的所有格子的总面积 。

 由上图我们可以得到二维差分的定义：在二维情况下，差分就变成了相邻a[][]的"面积差"，计算公式是：

b [ i ] [ j ] = a [ i ] [ j ] − a [ i − 1 ] [ j ] − a [ i ] [ j − 1 ] + a [ i − 1 ] [ j − 1 ] 

即利用上图红色大面积 a [ i ] [ j ] 减去两个小面积 a [ i − 1 ] [ j ] 、 a [ i ] [ j ] ，由于两个小面积公共的部分a[i-1][j -1]被减去了 2 次，故要加回来 1 次 a [ i − 1 ] [ j − 1 ] 。

两个端点的修改操作如下：

b[x1][y1] += c; //  二维区间的起点
b[x1][y2 + 1] -= c; // 把 x看成常数，y从 y1 到 y2
b[x2 + 1][y1] -= c;// 把 y看成常熟，x从 x1 到 x2
b[x2 + 1][y2 + 1] += c;// 由于前面两式把 c 减去了 2 次，故要加回 1 次

本题AC代码：

#include<iostream>
#include<cstdio>
using namespace std;
#define MAXN 1010
int n,m,x1,x2,y1,y2;
int a[MAXN][MAXN];

int main() {
    cin >>n>>m;
    for (int i=1;i<=m;i++) {
        cin >>x1>>y1>>x2>>y2;
        
        a[x1][y1]++;     //修改操作
        a[x1][y2+1]--;
        a[x2+1][y1]--;
        a[x2+1][y2+1]++
    }
    for (int i=1;i<=n;i++,printf('\n'))
        for (int j=1,j<=n;j++) {
            a[i][j] += a[i-1][j] + a[i][j-1] - a[i-1][j-1]; //求前缀和
            cout << a[i][j];
        }
    return 0;
}

引用：

【详解】手撕 一维、二维、三维差分数组原理（附图解，模板，例题分析）-CSDN博客