【模板】差分

一维差分：

描述

给你一个长度为n的正数数组a_1,a_2,...a_na1​,a2​,...an​.

接下来对这个数组进行m次操作，每个操作包含三个参数l,r,k，代表将数组中a_l,...a_ral​,...ar​部分都加上k。

请输出操作后的数组。

输入描述：

第一行包含两个整数n和m。
第二行包含n个整数表示a_1,...a_na1​,...an​
接下来是m行，每行三个整数，分别代表每次操作的参数l,r,k.

输出描述：

输出1行，表示m次操作后的a_1,...a_na1​,...an​

示例1

输入：

3 2
1 2 3
1 2 4
3 3 -2

复制输出：

5 6 1

#include<stdio.h>
int a[100005];
long long difference[100005];
int main()
{
    int n,m;
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++)
    {
        scanf("%d",&a[i]);
    }
    difference[1]=a[1];
    for(int i=2;i<=n;i++)
    {
        difference[i]=a[i]-a[i-1];
    }
    for(int i=1;i<=m;i++)
    {
        int l,r,k;
        scanf("%d%d%d",&l,&r,&k);
        difference[l]=difference[l]+k;
        difference[r+1]-=k;
    }
    printf("%lld",difference[1]);
    long long sum=difference[1];
    for(int i=2;i<=n;i++)
    {
        sum+=difference[i];
        printf(" %lld",sum);
    }
    return 0;
}

二维差分

描述

给你一个n行m列的矩阵，下标从1开始。
接下来有q次操作，每次操作输入5个参数x1, y1, x2, y2, k
表示把以(x1, y1)为左上角,(x2,y2)为右下角的子矩阵的每个元素都加上k，
请输出操作后的矩阵。

输入描述：

第一行包含三个整数n,m,q.
接下来n行，每行m个整数，代表矩阵的元素

接下来q行，每行5个整数x1, y1, x2, y2, k，分别代表这次操作的参数

输出描述：

输出n行，每行m个数，每个数用空格分开，表示这个矩阵。

示例1

输入：

2 3 4
1 2 3
4 5 6
1 1 2 2 3
1 2 2 3 -1
1 1 1 3 4
1 1 2 1 1

复制输出：

9 8 6
8 7 5

#include<stdio.h>
long long a[1005][1005];//表示原矩阵是差分矩阵的前缀和
long long difference[1005][1005];//表示前缀和的差分
int main()
{
    int n,m,q;
    scanf("%d%d%d",&n,&m,&q);
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=m;j++)
        {
            scanf("%lld",&a[i][j]);
            difference[i][j]=a[i][j]-a[i][j-1]-a[i-1][j]+a[i-1][j-1];
            //有前缀和矩阵得到该矩阵的具体值
        }
    }
    for(int i=1;i<=q;i++)
    {
        int x1,y1,x2,y2,k;
        scanf("%d%d%d%d%d",&x1,&y1,&x2,&y2,&k);
        //如果是difference（i，j）处加上K,也就是说从（i，j)位置到右下角所有的值都会加上k
        //因为要从（x1,y1)到（x2,y2)所以要减去（x1,y2+1)和（y2+1,x1),由于从（x2+1,y2+1)减掉了两个k所以要加上一个k
        difference[x1][y1]+=k;
        difference[x1][y2+1]-=k;
        difference[x2+1][y1]-=k;
        difference[x2+1][y2+1]+=k;
    }
   for(int i=1;i<=n;i++)
   {
       for(int j=1;j<=m;j++)
       {
           difference[i][j]+=difference[i-1][j]+difference[i][j-1]-difference[i-1][j-1];
           if(j==1)
           {
               printf("%lld",difference[i][j]);
           }
           else{
                printf(" %lld",difference[i][j]);
           }
       }
       printf("\n");
   }
    
    return 0;
}