差分

• 概述：差分 是 与 前缀和 互逆 的一种运算 如果 数组 b 是 a 的 差分 数组，s 是 a的前缀和数组的 话 那么 b数组的前缀和 就是a 数组，所得到的a 数组的前缀和 对应 就是 s数组 ；s 数组 的差分数组就是 a ，a数组 的差分数组 是 b 数组
• 引入差分数组的目的：引入差分数组 是 为了 处理 一类问题 ：多次对给定居间内数 同时加上 一个常数c，求加完之后的数组。直接对 原数组进行遍历 然后做加法运算比较耗时，因此 引入差分数组 ，通过对差分数组进行处理较为简单，通过差分数组来 维护，最后通过 最后的差分数组求前缀和 回归 到现有数组

一维差分

Tips

• 定义： 如果存在数组 a[N] 那么 它的 当前项 与 前一项的 差 再作为 另一个数组b[N]当前项 的元素

• 通项公式： 求差分 b[i]=a[i]-a[i-1]; 求前缀和：a[i]=a[i-1]+b[i]

• 如何维护：假如 在一个区间 [l,r] 上 加上 c 那么我们的处理是

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

  其实这取决于 我们的目的 我们是要通过b 数组求前缀和 如果同时在一个区间上加上一个数，那么 对应 差分 数组只需要 在区间第一个上 加上c就好 （因为 求前缀和的话每一次都会加上区间内 的第一个数，所以 l 处 加上c 后面都会加上c l之前无影响 ），但是那 r 后面的我们不想它 加上，所以 在 r+1处 减去一个 c 那么一个+c 一个减 c 就会为零 ，后边的不变

• 差分数组需要跟据最开始的a数组初始化

  // 可以根据 insert操作来进行 初始化
  //假设 a 数组 元素开始 全为 0 那么每次在 一个区间上（一个下标）加上当前元素 a[i];
  for(int i=1;i<=n;i++) insert(i,i,a[i]);
  

• 在通过 差分数组求前缀和的时候 可以 存到 原来的a 里面 ，也可以直接存到 b上 这两个等价

  // 存到 a数组
   for(int i=1;i<=n;i++)  a[i]=a[i-1]+b[i];
  // 存到 b数组
  for(int i=1;i<n;i++)  b[i]+=b[i-1];    
  

模板题

• 题目： 输入一个长度为n的整数序列。

       接下来输入m个操作，每个操作包含三个整数l, r, c，表示将序列中[l, r]之间的每个数加上c。
  

  ​ 请你输出进行完所有操作后的序列。

• 代码

  #include<iostream>
  using namespace std;
  int n,m;
  const int N=1e5+10;
  int a[N],b[N];
  void insert(int l,int r,int c)
  {
      b[l]+=c;
      b[r+1]-=c;
  }
  int main()
  {
      cin>>n>>m;
      for(int i=1;i<=n;i++) cin>>a[i];
      for(int i=1;i<=n;i++) insert(i,i,a[i]);  //利用 insert 
      while(m--)
      {
          int l,r,c;
          cin>>l>>r>>c;
          insert(l,r,c);
      }
      for(int i=1;i<=n;i++) a[i]=a[i-1]+b[i]; 
      for(int i=1;i<=n;i++) cout<<a[i]<<" ";
  
      return 0;
  }
  

二维差分

Tips

• 定义：使二维子矩阵的前缀和为 原来矩阵 的矩阵 是 差分矩阵

• 通项公式：cf[i][j]=a[i][j]-a[i-1][j]-a[i][j-1]+a[i-1][j-1] cf 为构造的差分矩阵 a 为 原来矩阵 当前元素减去左边元素再减去上边元素再加上左上角元素.

• 差分矩阵维护

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

• 差分矩阵 初始化

  for(int i-1;i<=n;i++)
      for(int j=1;j<=m;j++)
          insert(i,j,i,j,a[i][j]);
  // 假设 原来 数组a是0 往里边添加 它本来的元素 只不过是 在 一个区间内装  
  

模板题

• 输入一个n行m列的整数矩阵，再输入q个操作，每个操作包含五个整数x1, y1, x2, y2, c，其中(x1, y1)和(x2, y2)表示一个子矩阵的左上角坐标和右下角坐标。

  每个操作都要将选中的子矩阵中的每个元素的值加上c。

  请你将进行完所有操作后的矩阵输出。

• 代码

  #include<iostream>
  using namespace std;
  int n,m,q;
  const int N=1010;
  int a[N][N],b[N][N];
  void insertnum(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()
  {
      cin>>n>>m>>q;
      for(int i=1;i<=n;i++)
          for(int j=1;j<=m;j++)
          {
              cin>>a[i][j];
              insertnum(i,j,i,j,a[i][j]);
          }
  
          while(q--)
          {
              int x1,y1,x2,y2,c;
              cin>>x1>>y1>>x2>>y2>>c;
              insertnum(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]; // 已知b数组 求 一个新的a数组（原来a的值不会影响） 
                    /* Or  通项公式 变形   b[i][j] += b[i-1][j]+b[i][j-1]-b[i-1][j-1]   用b数组记录 输出b数组*/
                     cout<<a[i][j]<<" ";   
                  }
           puts("");        
         }
  
      return 0;
  }