AcWing学习——差分

1. 概念

差分其实就是前缀和的逆运算，已知a1、a2……an，构造b1、b2……bn，使得ai=b1+b2+……+bi，bj=aj-a(j-1)，A数组称为B数组的前缀和，B数组称为A数组的差分。

1.1. B数组称为A数组的差分

• b1=a1
• b2=a2-a1
• b3=a3-a2
• ……
• bn=an-a(n-1)

1.2. A数组称为B数组的前缀和

• a1=b1
• a2=b1+b2
• a3=b1+b2+b3
• ……
• an=b1+b2+……+bn

2. 思路

当我们需要使得A数组中下标从l到r的全部元素都加上c的时候，只需要为B数组中bl+c，这个时候会使得A数组中al往后的元素都加上c，而我们只需要加到r即可，那么就令B数组中b(r+1)-c即可，这个时候A数组中al到ar就全部加上了c。

利用差分，我们只需要O(1)的时间复杂度，就可以为某个数组中间某个连续区间全部加上一个固定的值。

在最开始，我们可以假设A数组全为0，那么此时B数组也全为0。当A数组最开始不全为0时，我们可以假设做了n次插入操作，第i次可以看作[i,i]区间+ai。

3. 公式模板

3.1. 一维差分

给区间[l, r]中的每个数加上c：

B[l] += c, B[r + 1] -= c

3.2. 二维差分

给以(x1, y1)为左上角，(x2, y2)为右下角的子矩阵中的所有元素加上c：

S[x1, y1] += c, S[x2 + 1, y1] -= c, S[x1, y2 + 1] -= c, S[x2 + 1, y2 + 1] += c

4. 例题

4.1. 797. 差分 - AcWing题库

#include <iostream>

using namespace std;

const int N = 100010;

int n, m;

int a[N], b[N];

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

int main()
{
    scanf("%d%d", &n, &m);
    
    for(int i = 1; i <= n; i++) scanf("%d", &a[i]);
    
    for(int i = 1; i <= n; i++) insert(i, i, a[i]);
    
    while(m--) 
    {
        int l, r, c;
        scanf("%d%d%d", &l, &r, &c);
        insert(l, r, c);
    }
    
    for(int i = 1; i <= n; i++) b[i] += b[i - 1];
    
    for(int i = 1; i <= n; i++) printf("%d ", b[i]);
    
    return 0;
}

4.2. 798. 差分矩阵 - AcWing题库

#include <iostream>

const int N = 1010;

int n, m, q;

int a[N][N], b[N][N];

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

int main()
{
    scanf("%d%d%d", &n, &m, &q);
    
    for(int i = 1; i <= n; i++)
        for(int j = 1; j <= m; j++)
            scanf("%d", &a[i][j]);
            
    for(int i = 1; i <= n; i++)
        for(int j = 1; j <= m; j++)
            insert(i, j, i, j, a[i][j]);
            
    while(q--)
    {
        int x1, y1, x2, y2, c;
        scanf("%d%d%d%d%d", &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++)
            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 <= m; j++)
            printf("%d ", b[i][j]);
        puts("");
    }
    
    return 0;
}