前言：

好几个星期前学的，逐渐淡忘了，今日再次遇见，专门写一篇博客介绍很好用的一个算法–差分

概述:

差分算法适用于区间加减一个数，是前缀和的逆运算，二者经常出现在同一题目。

同时差分和前缀和一样分为一维差分与二维差分，下面将用题目带大家了解差分

实践:

一维差分

一维差分核心公式

1
2
a[l]+=w;//注意是对差分数组进行操作
a[r+1]-=w;

题目:小明的彩灯

小明拥有N个彩灯，第i个彩灯的初始亮度为ai。

小明将进行Q次操作，每次操作可选择一段区间，并使区间内彩灯的亮度+x（x可能为负数）。

求Q次操作后每一个彩灯的亮度（若彩灯亮度为负数则输出为0）

代码实现: 差分+前缀和

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
#include<bits/stdc++.h>
using namespace std;
const int N=1e5;
int s[N],a[N];
void insert(int l,int r,int w)//进行差分，使得区间加减w
{
    a[l]+=w;
    a[r+1]-=w;

}
int main()
{
    int n,q;
    cin>>n>>q;
    for(int i=1;i<=n;i++)cin >>s[i];
    for(int i=1;i<=n;i++)insert(i,i,s[i]);//获得差分数组
    while(q--)//进行操作
    {
        int l,r,w;
        cin>>l>>r>>w;
        insert(l,r,w);
    }
    for(int i=1;i<=n;i++)//进行前缀和
        a[i]+=a[i-1];
    for(int i=1;i<=n;i++) {
        if(a[i]<=0)cout<<0<<' ';
        else cout<<a[i]<<' ';
    }
    return 0;
}

二维差分

二维差分核心公式

1
2
3
4
b[x1][y1]+=1;
b[x2+1][y1]-=1;
b[x1][y2+1]-=1;
b[x2+1][y2+1]+=1;

题目:地毯

题解：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
#include<bits/stdc++.h>
using namespace std;
const int N=1005,M=1005;
int b[N][N];
void insert(int x1,int y1,int x2,int y2)
{
    b[x1][y1]+=1;
    b[x2+1][y1]-=1;
    b[x1][y2+1]-=1;
    b[x2+1][y2+1]+=1;
}
int main()
{
    int n,m;
    cin>>n>>m;
    while(m--)
    {
        int x1,y1,x2,y2;
        cin>>x1>>y1>>x2>>y2;
        insert(x1,y1,x2,y2);
    }
    for(int i=1;i<=n;i++)
        for(int j=1;j<=n;j++)
        {
            b[i][j]+=b[i-1][j]+b[i][j-1]-b[i-1][j-1];
        }
    for(int i=1;i<=n;i++) {
        for (int j = 1; j <= n; j++)
            cout << b[i][j] << ' ';
        cout<<endl;
    }

    return 0;
}