差分(ACWing算法基础)

wuchangjian2021-11-03 21:38:19编程学习

一维差分

知识
已知a1、a2、…、an,构造数组b,使得ai=b1+b2+…+bi。
a是b的前缀和,b是a的差分。

b1=a1,
b2=a2-a1;
b3=a3-a2;
bn=an-an-1。

要使 [l,r]内a数组的全部值加c,只进行bl+c和br+1-c处理即可。

题目描述
输入:

  1. 一个长度为n的整数序列
  2. m个操作,每个操作包含l,r,c三个数,将序列中[l,r]之间的每个数加c

代码实现

#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);
 //输入前缀和a[]
 for(int i=1;i<=n;i++)scanf("%d",&a[i]);

 //计算差分b[]
 //注意理解
 //b[i]+=a[i];
 //b[i+1]-=a[i];
 for(int i=1;i<=n;i++)insert(i,i,a[i]);
 
 //进行m次操作
 while(m--)
 {
   int l,r,c;
   scanf("%d%d%d",&l,&r,&c);
   insert(l,r,c);
 }
 
 //计算经过处理后b[]的前缀和数组(前缀和数组每个数都加了n)
 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;
}

二维差分

在这里插入图片描述

在这里插入图片描述
问题描述
输入:
一个n行m列的整数矩阵
q个操作,每个操作包含5个整数:x1、y1、x2、y2、c。(x1,y1)和(x2,y2)表示一个子矩阵的左上角和右下角的坐标。每个操作都进行将选中的子矩阵中的每个元素值加c。

#include<iostream>
using namespace std;

const int N = 1010;
int n,m,q;//n为矩阵的行数,m为矩阵的列数
int a[N][N],b[N][N];//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[x2][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]);
       
   //进行插入操作初始化差分数组b[][]
   for(int i=1;i<=n;i++)
      for(int j=1;j<=m;j++)
       insert(i,j,i,j,a[i][j]);

   //q次输入区间进行插入操作
   while(q--)
   {
     int x1,y1,x2,y2,c;
     cin>>x1>>y1>>x2>>y2;
     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;
}

相关文章

linux 内核优化系统初始化

整理资料,发现只记录了参数,没有备注,故重新整...

中国半导体设备行业需求状况与投资前景展望分析报告2022版

中国半导体设备行业需求状况与投资前景展望分析报告2022版 HS--HS--HS--HS...

发表评论    

◎欢迎参与讨论,请在这里发表您的看法、交流您的观点。