差分

目录

• 一、一维差分
  • 1.一维差分的定义
  • 2.一维差分的操作
  • 3.一维差分相关的例题
• 二、二维差分
  • 1.二维差分的重要操作
  • 2.二维差分例题

一、一维差分

1.一维差分的定义

给定一个数组A它的差分数组B的定义为：$$B[i]=A[i]-A[i-1](2<=i<=n)$$

2.一维差分的操作

一维差分可以让我们在一段区间内加上指定的数，其它位置不变，差分可以帮助我们把“区间操作”变成对差分数组的“单点操作”，降低我们的求解难度。

比如：让我们在a数组的l-r这个区间加上d的话我们就可以先求出a数组的差分数组b，然后在b[l]加上d,然后再在b[r+1]的地方减去d即可。因为差分的前缀和就是原数组（相当于前缀和的逆运算），我们在b[l]的地方加上d通过前缀和求原数组的时候就相当于在下标为l（包括l）之后的数全部加上d，又因为我们只需要在l-r这个区间加上d，所以我们就可以在r+1的地方再减去d即可。

b[l]+=d;
b[r+1]-=d;

3.一维差分相关的例题

AcWing一维差分例题
思路：这个其实就是差分的板子题，直接根据上面讲的写完add函数就可以了

#include 
#include 
#include 
using namespace std;

const int N = 1e6 + 10;
int a[N], b[N];

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

int main()
{
    std::ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int n, m;
    cin >> n >> m;
    for (int i = 1; i <= n; i++)
        cin >> a[i], add(i, i, a[i]);
    while (m--)
    {
        int l, r, c;
        cin >> l >> r >> c;
        add(l, r, c);
    }
    for (int i = 1; i <= n; i++)
        b[i] += b[i - 1];
    for (int i = 1; i <= n; i++)
        cout << b[i] << ' ';
    return 0;
}

算法竞赛进阶指南-IncDec序列
思路：这个题的话，我们可以先求出a的差分数组b，这样的的话我们直接对差分数组b进行操作即可，我们可以令差分数组下标为n+1的地方也为0，这样的话我们就从下标是1~n+1的数组b中任意选两个数一个加一，另一个减一。我们的目的就是把$b_1$,$b_2$,…,$b_n$全部变成0，然后我们可以得到一个序列a，就是由n个由$b_1$组成的。
此时我们有四种选两个数的选法
1.第一种是，我们可以选$b_i$和$b_j$（2 <= i,j <= n），这样的话我们可以在保证$b_i$和$b_j$一正一负的情况下，尽量多采取这种情况可以更快的接近目标。
2.第二种是选$b_1$和$b_j$其中(2 <= j <= n)
3.第三种是选$b_i$和$b_{n+1}$其中（2 <= i <= n）
4.第四种是选择$b_1$和$b_{n+1}$这两个数，但是这么选没有意义，不会对结果造成影响，但是会浪费一次操作机会，所以选择4肯定不是最小操作次数。
我们可以把差分数组中的大于0的数求和位p，小于0的数的值求和绝对值为q，最小的操作次数就是$min(p,q)+|p-q|$,那么能有几种情况呢，只在选择2和3的时候我们才有更多种的情况，那么情况的种数就是$|p-q|+1$,然后我们就可以写出代码。

#include 
#include 
using namespace std;

const int N = 1e6 + 10;
long long a[N],b[N];

int main()
{
    int n;
    cin>>n;
    for(int i=1;i<=n;i++)   cin>>a[i];
    for(int i=1;i<=n;i++)   b[i]=a[i]-a[i-1];
    long long sum1=0,sum2=0;
    for(int i=2;i<=n;i++)
    {
        if(b[i]>0)  sum1+=b[i];
        else        sum2+=abs(b[i]);
    }
    cout<<min(sum1,sum2)+abs(sum1-sum2)<abs(sum1-sum2)+1<return 0;
}

算法竞赛进阶指南-最高的牛
思路：这个题的话我们不是很容易想到差分，但是我们仔细分析的话就会发现，如果两头牛之间如果可以看见的话就说明两头牛之间的牛的身高肯定要比端点的两头牛要矮，这样的话我们一开始可以设定一个差分数组，发它们的值全部赋值成最高的那头牛的高度，，再根据我们的m个关系把原数组l+1到r之间的数全部减去一即可，及$a_{l+1}$--，$a_r$++，然后通过前缀和求出原数组及为答案数组。（此题有坑点就是会重复需用set去重）。

#include 
#include 
#include 
#include 
using namespace std;

const int N = 1e6 + 10;
int a[N];

int main()
{
    std::ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int n, p, h, m;
    cin >> n >> p >> h >> m;
    a[1] = h;
    setint, int>> se;
    for (int i = 1, l, r; i <= m; i++)
    {
        cin >> l >> r;
        if (l > r)
            swap(l, r);
        if (!se.count({l, r}))
        {
            se.insert({l, r});
            a[l + 1]--;
            a[r]++;
        }
    }

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

二、二维差分

1.二维差分的重要操作

可以类比一维差分就是在一个区间内加上一个c，比如我们可以在a数组以x1,y1为左上角，x2,y2为右下角，在这个范围内加上一个数c，这样的话，我们就可以推出它的公式

    b[x1][y1] += c;
    b[x1][y2 + 1] -= c;
    b[x2 + 1][y1] -= c;
    b[x2 + 1][y2 + 1] += c;

2.二维差分例题

AcWing二维差分例题
思路：我们可以求出差分数组进行单点操作，然后利用我们上一篇讲到的二维前缀和的公式求出原数组输出即可

#include 
#include 
#include 
using namespace std;

const int N = 1e3 + 10;
int a[N][N], b[N][N];

void add(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()
{
    std::ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int n, m, q;
    cin >> n >> m >> q;
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=m;j++)
        {
            cin>>a[i][j];
            add(i,j,i,j,a[i][j]);
        }
    }

    while(q--)
    {
        int x1,x2,y1,y2,c;
        cin>>x1>>y1>>x2>>y2>>c;
        add(x1,y1,x2,y2,c);
    }

    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=m;j++)
        {
            a[i][j] = a[i-1][j] + a[i][j-1] - a[i-1][j-1] + b[i][j];
        }
    }

    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=m;j++)
        {
            cout<' ';
        }
        cout<return 0;
}