差分 --算法竞赛专题解析(32)

本系列文章将于2021年整理出版。前驱教材:《算法竞赛入门到进阶》 清华大学出版社
网购:京东 当当   作者签名书:点我
有建议请加QQ 群:567554289

文章目录

  • 1. 一维差分
    • 1.1 一维差分的概念
    • 1.2 差分的局限性
  • 2. 二维差分
    • 2.1 用差分数组的递推公式求前缀和
    • 2.2 直接计算前缀和
  • 3. 三维差分
  • 4. 差分习题

   差分是一种处理数据的巧妙而简单的方法,它应用于区间的修改和询问问题。把给定的数据元素集A分成很多区间,对这些区间做很多次操作,每次操作是对某个区间内的所有元素做相同的加减操作,若一个个地修改这个区间内的每个元素,非常耗时。引入“差分数组”D,当修改某个区间时,只需要修改这个区间的“端点”,就能记录整个区间的修改,而对端点的修改非常容易,是 O ( 1 ) O(1) O(1)复杂度的。当所有的修改操作结束后,再利用差分数组,计算出新的A。
  数据A可以是一维的线性数组 a [ ] a[] a[]、二维矩阵 a [ ] [ ] a[][] a[][]、三维立体 a [ ] [ ] [ ] a[][][] a[][][]。相应地,定义差分数组 D [ ] 、 D [ ] [ ] 、 D [ ] [ ] [ ] D[]、D[][]、D[][][] D[]D[][]D[][][]。一维差分很容易理解,二维和三维需要一点想象力。

1. 一维差分

1.1 一维差分的概念

   讨论这样一个场景:
   (1)给定一个长度为n的一维数组 a [ ] a[] a[],数组内每个元素有初始值。
   (2)修改操作:做m次区间修改,每次修改对区间内所有元素做相同的加减操作。例如第 i i i次修改,把区间 [ L i , R i ] [Li, Ri] [Li,Ri]内所有元素加上 d i di di
   (3)询问操作:询问一个元素的新值是多少。
   如果简单地用暴力法编码,那么每次修改的复杂度是 O ( n ) O(n) O(n)的,m次修改共 O ( m n ) O(mn) O(mn),总复杂度 O ( m n ) O(mn) O(mn),效率很差。利用差分法,可以把复杂度减少到 O ( m + n ) O(m+n) O(m+n)
   在差分法中,用到了两个数组:原数组 a [ ] a[] a[]、差分数组 D [ ] D[] D[]
   差分数组D[]的定义是 D [ k ] = a [ k ] − a [ k − 1 ] D[k] = a[k] - a[k-1] D[k]=a[k]a[k1],即原数组 a [ ] a[] a[]的相邻元素的差。从定义可以推出 a [ k ] = D [ 1 ] + D [ 2 ] + . . . + D [ k ] a[k] = D[1] + D[2] + ... + D[k] a[k]=D[1]+D[2]+...+D[k] ,也就是说, a [ ] a[] a[] D [ ] D[] D[]的前缀和。这个公式揭示了 a [ ] a[] a[] D [ ] D[] D[]的关系,“差分是前缀和的逆运算”,它把求 a [ k ] a[k] a[k]转化为求D的前缀和。为加深对前缀和的理解,可以把每个 D [ ] D[] D[]看成一条直线上的小线段,它的两端是相邻的 a [ ] a[] a[];这些小线段相加,就得到了从起点开始的长线段 a [ ] a[] a[]
   注意, a [ ] a[] a[] D [ ] D[] D[]的值都可能为负,下面图中所有的 D [ ] D[] D[]都是长度为正的线段,只是为了方便图示。

图1 把每个D[]看成小线段,把每个a[]看成从a[1]开始的小线段的和

  
  如何用差分数组记录区间修改?为什么利用差分数组能提升修改的效率呢?
  把区间 [ L , R ] [L, R] [L,R]内每个元素加上 d d d,对应的 D [ ] D[] D[]做以下操作:
  (1)把 D [ L ] D[L] D[L]加上 d d d

     D[L] += d

  (2)把 D [ R + 1 ] D[R+1] D[R+1]减去 d d d

     D[R+1] -= d

  每次操作只需要修改区间 [ L , R ] [L, R] [L,R]的两个端点的 D [ ] D[] D[]值,复杂度是 O ( 1 ) O(1) O(1)的。经过这种操作后,原来直接在 a [ ] a[] a[]上做的复杂度为 O ( n ) O(n) O(n)的区间修改操作,就变成了在 D [ ] D[] D[]上做的复杂度为 O ( 1 ) O(1) O(1)的端点操作。
  利用 D [ ] D[] D[],能精确地实现只修改区间内元素的目的,而不会修改区间外的 a [ ] a[] a[]值。因为前缀和 a [ x ] = D [ 1 ] + D [ 2 ] + . . . + D [ x ] a[x] = D[1] + D[2] + ... + D[x] a[x]=D[1]+D[2]+...+D[x],有:
  (1) 1 ≤ x < L 1 ≤ x < L 1x<L,前缀和 a [ x ] a[x] a[x]不变;
  (2) L ≤ x ≤ R L ≤ x ≤ R LxR,前缀和 a [ x ] a[x] a[x]增加了 d d d
  (3) R < x ≤ N R < x ≤ N R<xN,前缀和 a [ x ] a[x] a[x]不变,因为被 D [ R + 1 ] D[R+1] D[R+1]中减去的 d d d抵消了。
  完成区间修改并得到 D [ ] D[] D[]后,最后用 D [ ] D[] D[]计算 a [ ] a[] a[],复杂度是 O ( n ) O(n) O(n)的。m次区间修改和1次查询,总复杂度为 O ( m + n ) O(m + n) O(m+n),比暴力法的 O ( m n ) O(mn) O(mn)好多了。
  下面给出一个例题。


Color the ball hdu 1556 http://acm.hdu.edu.cn/showproblem.php?pid=1556
问题描述:N个气球排成一排,从左到右依次编号为1, 2, 3 … N。每次给定2个整数L, R(L<= R),lele从气球L开始到气球R依次给每个气球涂一次颜色。但是N次以后lele已经忘记了第I个气球已经涂过几次颜色了,你能帮他算出每个气球被涂过几次颜色吗?
输入:每个测试实例第一行为一个整数N,(N <= 100000)。接下来的N行,每行包括2个整数L, R(1 <= L<= R<= N)。当N = 0,输入结束。
输出:每个测试实例输出一行,包括N个整数,第I个数代表第I个气球总共被涂色的次数。


  这个例题是简单差分法的直接应用,下面给出代码。代码第13、14行是区间修改,第17行的 a [ i ] = a [ i − 1 ] + D [ i ] a[i] = a[i-1] + D[i] a[i]=a[i1]+D[i],即利用 D [ ] D[] D[]求得了最后的 a [ ] a[] a[]。这个式子就是 a [ i ] − a [ i − 1 ] = D [ i ] a[i] - a[i-1] = D[i] a[i]a[i1]=D[i],它是差分数组的定义。
  注意 a [ ] a[] a[]的计算方法。 a [ i ] = a [ i − 1 ] + D [ i ] a[i] = a[i-1] + D[i] a[i]=a[i1]+D[i]是一个递推公式,通过它能在一个 i i i循环中求得所有的 a [ ] a[] a[]。如果不用递推,而是直接用前缀和 a [ k ] = D [ 1 ] + D [ 2 ] + . . . + D [ k ] a[k]=D[1] + D[2] + ... + D[k] a[k]=D[1]+D[2]+...+D[k] 来求所有的 a [ ] a[] a[],就需要用两个循环 i 、 k i、k ik

//hdu 1556用差分数组求解
#include<bits/stdc++.h>
using namespace std;
const int Maxn = 100010;
int a[Maxn],D[Maxn];               //a是气球,D是差分数组int main(){int n;while(~scanf("%d",&n)) { memset(a,0,sizeof(a)); memset(D,0,sizeof(D));for(int i=1;i<=n;i++){int L,R; scanf("%d%d",&L,&R);D[L]++;                 //区间修改,这里d=1D[R+1]--;}
//小技巧:17行到20行,把a[]改成D[]也行for(int i=1;i<=n;i++){              //求原数组a[i] = a[i-1] + D[i];           //差分。求前缀和a[],a[i]就是气球i的值if(i!=n)  printf("%d ", a[i]);  //逐个打印结果else      printf("%d\n",a[i]);}        }return 0;
}

  上面的代码用了一个小技巧,可以省掉 a [ ] a[] a[],从而节省空间。在17行后求原数组 a [ ] a[] a[]的时候,在推导式子 a [ i ] = a [ i − 1 ] + D [ i ] a[i] = a[i-1] + D[i] a[i]=a[i1]+D[i]时,把已经使用过的较小的 D [ ] D[] D[]直接当成 a [ ] a [] a[]即可。把第17~20行的 a [ ] 改 为 D [ ] a[]改为D[] a[]D[],也能通过。这个技巧在后面的二维差分、三维差分中也能用,节省一倍的空间。

1.2 差分的局限性

  读者已经注意到,利用差分数组 D [ ] D[] D[]可以把 O ( n ) O(n) O(n)的区间修改,变成 O ( 1 ) O(1) O(1)的端点修改,从而提高了修改操作的效率。
  但是,一次查询操作,即查询某个 a [ i ] a[i] a[i],需要用 D [ ] D[] D[]计算整个原数组 a [ ] a[] a[],计算量是 O ( n ) O(n) O(n)的,即一次查询的复杂度是 O ( n ) O(n) O(n)的。在上面的例题中,如果查询不是发生了一次,而是这样:有m次修改,有k次查询,且修改和查询的顺序是随机的。此时总复杂度是:m次修改复杂度 O ( m ) O(m) O(m),k次查询复杂度 O ( k n ) O(kn) O(kn),总复杂度 O ( m + k n ) O(m + kn) O(m+kn)。还不如直接用暴力法,总复杂度 O ( m n + k ) O(mn + k) O(mn+k)
  这种题型是“区间修改+单点查询”,用差分数组往往不够用。因为差分数组对“区间修改”很高效,但是对“单点查询”并不高效。此时需要用树状数组和线段树来求解,详情见第4章的树状数组、线段树专题。在树状数组专题中,重新讲解了hdu 1556这道例题。
  树状数组常常结合差分数组来解决更复杂的问题,见本博客的树状数组专题。差分数组也常用于“树上差分”,见本博客LCA专题的“树上差分”。

2. 二维差分

  从一维差分容易扩展到二维差分。一维是线性数组,一个区间 [ L , R ] [L, R] [L,R]有两个端点;二维是矩阵,一个区间由四个端点围成。
  下面给出一个模板题。


地毯 洛谷P3397 https://www.luogu.com.cn/problem/P3397
问题描述:在 n×n 的格子上有m个地毯。给出这些地毯的信息,问每个点被多少个地毯覆盖。
输入: 第一行是两个正整数n,m。接下来m行,每行2个坐标(x1, y1)和(x2, y2),代表一块地毯,左上角是(x1, y1),右下角是(x2, y2)。
输出: 输出n行,每行n个正整数。第i行第j列的正整数表示(i, j)这个格式被多少地毯覆盖。


  这一题是hdu 1556的二维扩展,其修改操作和查询操作完全一样。
  存储矩阵需要很大的空间。如果题目有空间限制,例如100M,那么二维差分能处理多大的n?定义两个二维矩阵 a [ ] [ ] 和 D [ ] [ ] a[][]和D[][] a[][]D[][],设矩阵的每个元素是2字节的 i n t int int型,可以计算出最大的n = 5000。不过,也可以不定义 a [ ] [ ] a[][] a[][],而是像一维情况下一样,直接用 D [ ] [ ] 来 表 示 a [ ] [ ] D[][]来表示a[][] D[][]a[][],这样能剩下一半的空间。
  在用差分之前,先考虑能不能用暴力法。每次修改复杂度是 O ( n 2 ) O(n^2) O(n2),共m次,总复杂度 O ( m × n 2 ) O(m×n^2) O(m×n2),超时。
  二维差分的复杂度是多少?一维差分的一次修改是 O ( 1 ) O(1) O(1)的,二维差分的修改估计也是 O ( 1 ) O(1) O(1)的;一维差分的一次查询是 O ( n ) O(n) O(n)的,二维差分是 O ( n 2 ) O(n^2) O(n2)的,所以二维差分的总复杂度是 O ( m + n 2 ) O(m + n^2) O(m+n2)。由于计算一次二维矩阵的值需要 O ( n 2 ) O(n^2) O(n2)次计算,所以二维差分已经达到了最好的复杂度。
  下面从一维差分推广到二维差分。
  (1)前缀和。
  在一维差分中,原数组 a [ ] a[] a[]是从第1个 D [ 1 ] D[1] D[1]开始的差分数组 D [ ] D[] D[]的前缀和: a [ k ] = D [ 1 ] + D [ 2 ] + . . . + D [ k ] a[k] = D[1] + D[2] + ... + D[k] a[k]=D[1]+D[2]+...+D[k]
  在二维差分中, a [ ] [ ] a[][] a[][]是差分数组 D [ ] [ ] D[][] D[][]的前缀和,即由原点坐标 ( 1 , 1 ) (1, 1) (1,1)和坐标 ( i , j ) (i, j) (i,j)围成的矩阵中,所有的 D [ ] [ ] D[][] D[][]相加等于 a [ i ] [ j ] a[i][j] a[i][j]。为加深对前缀和的理解,可以把每个 D [ ] [ ] D[][] D[][]看成一个小格;在坐标 ( 1 , 1 ) 和 ( i , j ) (1, 1)和(i, j) (1,1)(i,j)所围成的范围内,所有小格子加起来的总面积,等于 a [ i ] [ j ] a[i][j] a[i][j]。下面的图中,每个格子的面积是一个 D [ ] [ ] D[][] D[][],例如阴影格子是 D [ i ] [ j ] D[i][j] D[i][j],它由4个坐标点定义: ( i − 1 , j ) 、 ( i , j ) 、 ( i − 1 , j − 1 ) 、 ( i , j − 1 ) (i-1, j)、(i, j)、(i-1, j-1)、(i, j-1) (i1,j)(i,j)(i1,j1)(i,j1)。坐标点 ( i , j ) (i, j) (i,j)的值是 a [ i ] [ j ] a[i][j] a[i][j],它等于坐标 ( 1 , 1 ) 和 ( i , j ) (1, 1)和(i, j) (1,1)(i,j)所围成的所有格子的总面积。图中故意把小格子画得长宽不同,是为了体现它们的面积不同。

图2 把每个a[][]看成总面积,把每个D[][]看成小格子的面积

  
  注意在一些题目中, D [ ] [ ] D[][] D[][]可以为负。图中把 D [ ] [ ] D[][] D[][]用“面积”来演示,而面积都是正的,这个图示只是为了加深对前缀和的理解。
  (2)差分的定义。在一维情况下, D [ i ] = a [ i ] − a [ i − 1 ] D[i] = a[i] - a[i-1] D[i]=a[i]a[i1]。在二维情况下,差分变成了相邻的 a [ ] [ ] a[][] a[][]的“面积差”,计算公式是: D [ i ] [ j ] = a [ i ] [ j ] – a [ i − 1 ] [ j ] – a [ i ] [ j − 1 ] + a [ i − 1 ] [ j − 1 ] D[i][j] = a[i][j] – a[i-1][j] – a[i][j-1] + a[i-1][j-1] D[i][j]=a[i][j]a[i1][j]a[i][j1]+a[i1][j1]。这个公式可以通过上面的图来观察。阴影方格表示 D [ i ] [ j ] D[i][j] D[i][j]的值,它的面积这样求:大面积 a [ i ] [ j ] a[i][j] a[i][j]减去两个小面积 a [ i − 1 ] [ j ] 、 a [ i ] [ j − 1 ] a[i-1][j]、a[i][j-1] a[i1][j]a[i][j1],由于两个小面积的公共面积 a [ i − 1 ] [ j − 1 ] a[i-1][j-1] a[i1][j1]被减了2次,所以需要加回来1次。
  (3)区间修改。在一维情况下,做区间修改只需要修改区间的两个端点的 D [ ] D[] D[]值。在二维情况下,一个区间是一个小矩阵,有4个端点,只需要修改这4个端点的 D [ ] [ ] D[][] D[][]值。例如坐标点 ( x 1 , y 1 ) (x1, y1) (x1,y1) ~ ( x 2 , y 2 ) (x2, y2) (x2,y2)定义的区间,对应4个端点的 D [ ] [ ] D[][] D[][]

D[x1][y1]     += d;     //二维区间的起点
D[x1][y2+1]   -= d;     //把x看成常数,y从y1到y2+1
D[x2+1][y1]   -= d;     //把y看成常数,x从x1到x2+1
D[x2+1][y2+1] += d;     //由于前两式把d减了2次,多减了1次,这里加1次回来

  下图是区间修改的图示。2个黑色点围成的矩形是题目给出的区间修改范围。只需要改变4个 D [ ] [ ] D[][] D[][]值,即改变图中的4个阴影块的面积。读者可以用这个图,观察每个坐标点的 a [ ] [ ] a[][] a[][]值的变化情况。例如符号“∆”标记的坐标 ( x 2 + 1 , y 2 ) (x2+1, y2) (x2+1,y2),它在修改的区间之外; a [ x 2 + 1 ] [ y 2 ] a[x2+1][y2] a[x2+1][y2]的值是从 ( 1 , 1 ) 到 ( x 2 + 1 , y 2 ) (1,1)到(x2+1, y2) (1,1)(x2+1,y2)的总面积,在这个范围内, D [ x 1 ] [ y 1 ] + d , D [ x 2 + 1 ] [ y 1 ] − d D[x1][y1]+d,D[x2+1][y1]-d D[x1][y1]+dD[x2+1][y1]d,两个 d d d抵消, a [ x 2 + 1 ] [ y 2 ] a[x2+1][y2] a[x2+1][y2]保持不变。

图3 二维差分的区间修改

  下面给出洛谷P3397的两种实现。

2.1 用差分数组的递推公式求前缀和

  前缀和 a [ ] [ ] a[][] a[][]的计算用到了递推公式:
     a [ i ] [ j ] = D [ i ] [ j ] + a [ i − 1 ] [ j ] + a [ i ] [ j − 1 ] − a [ i − 1 ] [ j − 1 ] ; a[i][j] = D[i][j] + a[i-1][j] + a[i][j-1] - a[i-1][j-1]; a[i][j]=D[i][j]+a[i1][j]+a[i][j1]a[i1][j1];
  16行到23行用 D [ ] [ ] D[][] D[][]推出 a [ ] [ ] a[][] a[][]并打印出来。
  为了节约空间,可以不定义 a [ ] [ ] a[][] a[][],而是把用过的 D [ ] [ ] D[][] D[][]看成 a [ ] [ ] a[][] a[][]。这个小技巧在一维差分中介绍过。

#include<bits/stdc++.h>
using namespace std;
int D[5000][5000];     //差分数组
//int a[5000][5000];   //原数组,不定义也行
int main(){int n,m;scanf("%d%d",&n,&m);while(m--){int x1,y1,x2,y2;scanf("%d%d%d%d",&x1,&y1,&x2,&y2);D[x1][y1]     += 1;        //计算差分数组D[x2+1][y1]   -= 1;D[x1][y2+1]   -= 1;D[x2+1][y2+1] += 1;}for(int i=1;i<=n;++i){   //根据差分数组计算原矩阵的值(想象成求小格子的面积和)for(int j=1;j<=n;++j){      //把用过的D[][]看成a[][],就不用再定义a[][]了//a[i][j] = D[i][j] + a[i-1][j] + a[i][j-1] - a[i-1][j-1];//printf("%d ",a[i][j]);  //这两行和下面两行的效果一样D[i][j] += D[i-1][j]+D[i][j-1]-D[i-1][j-1];printf("%d ",D[i][j]);}printf("\n");//换行}return 0;
}

2.2 直接计算前缀和

  其实不用递推公式,而是直接求前缀和也行。根据图2,前缀和是总面积,分别从 x x x方向和 y y y方向,用两次循环计算,并直接用 D [ ] [ ] D[][] D[][]记录结果,最后算出的 D [ ] [ ] D[][] D[][]就是 a [ ] [ ] a[][] a[][]

图4 在D[][]上计算前缀和

  以阴影处的 D [ 2 ] [ 2 ] D[2][2] D[2][2]为例,它最后的值代表 a [ 2 ] [ 2 ] a[2][2] a[2][2],是4个小格子的总面积:
     D [ 1 ] [ 1 ] + D [ 1 ] [ 2 ] + D [ 2 ] [ 1 ] + D [ 2 ] [ 2 ] D[1][1] + D[1][2] + D[2][1] + D[2][2] D[1][1]+D[1][2]+D[2][1]+D[2][2]
  计算过程是:
  (1)先累加计算 y y y方向,得:
     D [ 1 ] [ 2 ] = D [ 1 ] [ 1 ] + D [ 1 ] [ 2 ] 、 D [ 2 ] [ 2 ] = D [ 2 ] [ 1 ] + D [ 2 ] [ 2 ] D[1][2] = D[1][1]+ D[1][2]、D[2][2] = D[2][1]+ D[2][2] D[1][2]=D[1][1]+D[1][2]D[2][2]=D[2][1]+D[2][2]
  (2)再累加计算 x x x方向,得:
     D [ 2 ] [ 1 ] = D [ 1 ] [ 1 ] + D [ 2 ] [ 1 ] 、 D [ 2 ] [ 2 ] = D [ 1 ] [ 2 ] + D [ 2 ] [ 2 ] = D [ 1 ] [ 1 ] + D [ 1 ] [ 2 ] + D [ 2 ] [ 1 ] + D [ 2 ] [ 2 ] D[2][1]=D[1][1]+D[2][1]、D[2][2]=D[1][2]+D[2][2]= D[1][1]+D[1][2]+ D[2][1]+ D[2][2] D[2][1]=D[1][1]+D[2][1]D[2][2]=D[1][2]+D[2][2]=D[1][1]+D[1][2]+D[2][1]+D[2][2]
  实际上,在这个计算过程中, D [ 1 ] [ 1 ] 、 D [ 1 ] [ 2 ] 、 D [ 2 ] [ 1 ] 、 D [ 2 ] [ 2 ] D[1][1]、D[1][2]、D[2][1]、D[2][2] D[1][1]D[1][2]D[2][1]D[2][2]都更新了,计算结果代表了 a [ 1 ] [ 1 ] 、 a [ 1 ] [ 2 ] 、 a [ 2 ] [ 1 ] 、 a [ 2 ] [ 2 ] a[1][1]、a[1][2]、a[2][1]、a[2][2] a[1][1]a[1][2]a[2][1]a[2][2]
  把方法1代码的16-24行替换为下面的代码,最后得到的 D [ ] [ ] D[][] D[][]就是所有的前缀和,即最新的 a [ ] [ ] a[][] a[][]。请对照图2理解代码。

    for(int i=1; i<=n; ++i)           for(int j=1; j<n; ++j)        //注意这里是j<nD[i][j+1] += D[i][j];     //把i看成定值,先累加计算j方向for(int j=1; j<=n; ++j)for(int i=1; i<n; ++i)        //注意这里是i<nD[i+1][j] += D[i][j];     //把j看成定值,再累加计算i方向for(int i=1; i<=n; ++i) {         //打印for(int j=1; j<=n; ++j)printf("%d ",D[i][j]);printf("\n");                 //换行}

  对比这两种代码:
  (1)这两种代码的复杂度是一样的。从计算量上看,没有优劣之分。
  (2)代码2不如代码1清晰简洁,所以代码2这种写法一般也用不着。
  (3)代码2也有优点,它不需要用到递推公式,而是直接求前缀和。
  这里给出代码2这种方法,是为了在下一小节的三维差分中使用它。由于在三维情况下,差分数组的 D [ ] [ ] [ ] D[][][] D[][][]和原数组 a [ ] [ ] [ ] a[][][] a[][][]的递推公式很难写出来,所以用代码2这种方法更容易编码。

3. 三维差分

  三维差分的模板代码比较少见。
  三维差分比较复杂,请结合本节中的几何图进行理解。
  与一维差分、二维差分的思路类似,下面给出三维差分的有关特性。
  (1)元素的值用三维数组 a [ ] [ ] [ ] a[][][] a[][][]来定义,差分数组 D [ ] [ ] [ ] D[][][] D[][][]也是三维的。把三维差分想象成在立体空间上的操作。一维的区间是一个线段,二维是矩形,那么三维就是立体块。一个小立体块有8个顶点,所以三维的区间修改,需要修改8个 D [ ] [ ] [ ] D[][][] D[][][]值。
  (2)前缀和。
  在二维差分中, a [ ] [ ] a[][] a[][]是差分数组 D [ ] [ ] D[][] D[][]的前缀和,即由原点坐标 ( 1 , 1 ) (1, 1) (1,1)和坐标 ( i , j ) (i, j) (i,j)围成的矩阵中,所有的 D [ ] [ ] D[][] D[][](看成小格子)相加等于 a [ i ] [ j ] a[i][j] a[i][j](看成总面积)。
  在三维差分中, a [ ] [ ] [ ] a[][][] a[][][]是差分数组 D [ ] [ ] [ ] D[][][] D[][][]的前缀和。即由原点坐标 ( 1 , 1 , 1 ) (1, 1, 1) (1,1,1)和坐标 ( i , j , k ) (i, j, k) (i,j,k)所标记的范围中,所有的 D [ ] [ ] [ ] D[][][] D[][][]相加等于 a [ i ] [ j ] [ k ] a[i][j][k] a[i][j][k]。把每个 D [ ] [ ] [ ] D[][][] D[][][]看成一个小立方体;在坐标 ( 1 , 1 , 1 ) (1, 1, 1) (1,1,1) ( i , j , k ) (i, j, k) (i,j,k)所围成的空间中,所有小立体块加起来的总体积,等于 a [ i ] [ j ] [ k ] a[i][j][k] a[i][j][k]。每个小立方体由8个坐标点定义,见下面图中的坐标点。坐标点 ( i , j , k ) (i, j, k) (i,j,k)的值是 a [ i ] [ j ] [ k ] a[i][j][k] a[i][j][k] D [ i ] [ j ] [ k ] D[i][j][k] D[i][j][k]的值是图中小立方体的体积。

图5立体的坐标

  (3)差分的定义。在三维情况下,差分变成了相邻的 a [ ] [ ] [ ] a[][][] a[][][]的“体积差”。如何写出差分的递推计算公式?
  一维差分和二维差分的递推计算公式很好写。
  三维差分, D [ i ] [ j ] [ k ] D[i][j][k] D[i][j][k]的几何意义是图中小立方体的体积,它可以通过这个小立方体的8个顶点的值推出来。思路与二维情况下类似,二维的 D [ ] [ ] D[][] D[][]是通过小矩形的四个顶点的 a [ ] [ ] a[][] a[][]值来计算的。不过,三维情况下,递推计算公式很难写,8个顶点有8个 a [ ] [ ] [ ] a[][][] a[][][],把脑袋绕晕了也不容易写对。
上一小节的二维差分中,曾用过另一种方法,直接对D数组求前缀和。在三维情况下也可以用这种方法求前缀和,得到所有的 a [ ] [ ] [ ] a[][][] a[][][]的最新值。
  (4)区间修改。在三维情况下,一个区间是一个立方体,有8个顶点,只需要修改这8个顶点的 D [ ] [ ] [ ] D[][][] D[][][]值。例如坐标点 ( x 1 , y 1 , z 1 ) (x1, y1, z1) (x1,y1,z1) ~ ( x 2 , y 2 , z 2 ) (x2, y2, z2) (x2,y2,z2)定义的区间,对应8个 D [ ] [ ] [ ] D[][][] D[][][],请对照上面的图来想象它们的位置。

D[x1][y1][z1]       += d;   //前面:左下顶点,即区间的起始点
D[x2+1][y1][z1]     -= d;   //前面:右下顶点的右边一个点
D[x1][y1][z2+1]     -= d;   //前面:左上顶点的上面一个点
D[x2+1][y1][z2+1]   += d;   //前面:右上顶点的斜右上方一个点
D[x1][y2+1][z1]     -= d;   //后面:左下顶点的后面一个点
D[x2+1][y2+1][z1]   += d;   //后面:右下顶点的斜右后方一个点
D[x1][y2+1][z2+1]   += d;   //后面:左上顶点的斜后上方一个点
D[x2+1][y2+1][z2+1] -= d;   //后面:右上顶点的斜右上后方一个点,即区间终点的后一个点

下面给出一个三维差分的例题。


三体攻击 蓝桥杯2018年省赛A组
提交地址:https://www.lanqiao.cn/problems/180/learning/
问题描述:三体人将对地球发起攻击。为了抵御攻击,地球人派出了n = A × B × C 艘战舰,在太空中排成一个 A 层 B 行 C 列的立方体。其中,第 i 层第 j 行第 k 列的战舰(记为战舰 (i, j, k))的生命值为 s(i, j, k)。
三体人将会对地球发起 m 轮“立方体攻击”,每次攻击会对一个小立方体中的所有战舰都造成相同的伤害。具体地,第 t 轮攻击用 7 个参数 x1, x2, y1, y2, z1, z2, d 描述;
所有满足i∈[x1, x2], j∈[y1, y2], k∈[z1, z2] 的战舰 (i, j, k) 会受到 d 的伤害。如果一个战舰累计受到的总伤害超过其防御力,那么这个战舰会爆炸。
地球指挥官希望你能告诉他,第一艘爆炸的战舰是在哪一轮攻击后爆炸的。
输入:第一行包括 4 个正整数 A, B, C, m;
第二行包含 A × B × C 个整数,其中第 ((i − 1)×B + (j − 1)) × C + (k − 1)+1 个数为 s(i, j, k);
第 3 到第 m + 2 行中,第 (t − 2) 行包含 7 个正整数 x1, x2, y1, y2, z1, z2, d。
A × B × C ≤ 10^6, m ≤ 10^6, 0 ≤ s(i, j, k), d ≤ 10^9。
输出:输出第一个爆炸的战舰是在哪一轮攻击后爆炸的。保证一定存在这样的战舰。


  首先看数据规模,有 n = 1 0 6 n=10^6 n=106个点, m = 1 0 6 m=10^6 m=106次攻击,如果用暴力法,统计每次攻击后每个点的生命值,那么复杂度是 O ( m n ) O(mn) O(mn)的,超时。
  本题适合用三维差分,每次攻击只修改差分数组 D [ ] [ ] [ ] D[][][] D[][][],一次修改的复杂度是 O ( 1 ) O(1) O(1) m m m次修改的总复杂度只有 O ( m ) O(m) O(m)
  但是光用差分数组并不能解决问题。因为在差分数组上查询区间内的每个元素是否小于0,需要用差分数组来计算区间内每个元素的值,复杂度是 O ( n ) O(n) O(n)的。合起来的总复杂度还是O(mn)的,跟暴力法的复杂度一样。
  本题需要结合第二个算法:二分法。从第1次修改到第m次修改,肯定有一次修改是临界点。在临界点前,没有负值(战舰爆炸);在临界点后,出现了负值,且后面一直有负值。那么对m进行二分,就能在 O ( l o g m ) O(logm) O(logm)次内找到这个临界点,这就是答案。总复杂度 O ( n l o g m ) O(nlogm) O(nlogm)
下面给出代码。其中check()函数包含了三维差分的全部内容。代码有几个关键点:
  (1)没有定义 a [ ] [ ] [ ] a[][][] a[][][],而是用 D [ ] [ ] [ ] D[][][] D[][][]来代替。
  (2)压维。直接定义三维差分数组 D [ ] [ ] [ ] D[][][] D[][][]不太方便。虽然坐标点总数量 n = A × B × C = 1 0 6 n = A × B × C = 10^6 n=A×B×C=106比较小,但是每一维都需要定义到 1 0 6 10^6 106,那么总空间就是 1 0 18 10^{18} 1018。为避免这一问题,可以把三维坐标压维成一维数组 D [ ] D[] D[],总长度仍然是 1 0 6 10^6 106的。这个技巧很有用。实现函数是num(),它把三维坐标 ( x , y , z ) (x, y, z) (x,y,z)变换为一维坐标 h = ( x − 1 ) ∗ B ∗ C + ( y − 1 ) ∗ C + ( z − 1 ) + 1 h = (x-1)*B*C + (y-1)*C + (z-1) + 1 h=(x1)BC+(y1)C+(z1)+1,当 x 、 y 、 z x、y、z xyz的取值范围分别是1 ~ A、1 ~ B、1 ~ C时, h h h的范围是1 ~ A × B × C。
  如果希望按C语言的习惯从0开始, x 、 y 、 z x、y、z xyz的取值范围分别是0 ~ A-1、0 ~ B-1、0 ~ C-1,h范围是0 ~ A × B × C-1,就把式子改为: h = x ∗ B ∗ C + y ∗ C + z h = x*B*C + y*C + z h=xBC+yC+z
  同理,二维坐标 ( x , y ) (x, y) (x,y)也可以压维成一维 h = ( x − 1 ) ∗ B + ( y − 1 ) + 1 h = (x-1)*B + (y-1) + 1 h=(x1)B+(y1)+1,当 x 、 y x、y xy的取值范围分别是1 ~ A、1 ~ B时, h h h的范围是1 ~ A × B。
  (3)check()中19-26行,在 D [ ] D[] D[]上记录区间修改。
  (4)check()中29-40行的3个for循环计算前缀和,原理见二维差分的代码2。它分别从 x 、 y 、 z x、y、z xyz三个方向累加小立方体的体积,计算出所有的前缀和。

#include<stdio.h>int A,B,C,n,m;
const int Maxn = 1000005;
int s[Maxn];   //存储舰队生命值
int D[Maxn];   //三维差分数组(压维);同时也用来计算每个点的攻击值
int x2[Maxn], y2[Maxn], z2[Maxn]; //存储区间修改的范围,即攻击的范围
int x1[Maxn], y1[Maxn], z1[Maxn]; int d[Maxn];                    //记录伤害,就是区间修改
int num(int x,int y,int z) {  
//小技巧:压维,把三维坐标[(x,y,z)转为一维的((x-1)*B+(y-1))*C+(z-1)+1if (x>A || y>B || z>C) return 0;return ((x-1)*B+(y-1))*C+(z-1)+1;
}
bool check(int x){              //做x次区间修改。即检查经过x次攻击后是否有战舰爆炸for (int i=1; i<=n; i++)  D[i]=0;  //差分数组的初值,本题是0for (int i=1; i<=x; i++) {         //用三维差分数组记录区间修改:有8个区间端点D[num(x1[i],  y1[i],  z1[i])]   += d[i];D[num(x2[i]+1,y1[i],  z1[i])]   -= d[i];D[num(x1[i],  y1[i],  z2[i]+1)] -= d[i];D[num(x2[i]+1,y1[i],  z2[i]+1)] += d[i];D[num(x1[i],  y2[i]+1,z1[i])]   -= d[i];D[num(x2[i]+1,y2[i]+1,z1[i])]   += d[i];D[num(x1[i],  y2[i]+1,z2[i]+1)] += d[i];D[num(x2[i]+1,y2[i]+1,z2[i]+1)] -= d[i];}//下面从x、y、z三个方向计算前缀和for (int i=1; i<=A; i++)for (int j=1; j<=B; j++)for (int k=1; k<C; k++)        //把x、y看成定值,累加z方向D[num(i,j,k+1)] += D[num(i,j,k)];for (int i=1; i<=A; i++)for (int k=1; k<=C; k++)for (int j=1; j<B; j++)        //把x、z看成定值,累加y方向D[num(i,j+1,k)] += D[num(i,j,k)];for (int j=1; j<=B; j++)for (int k=1; k<=C; k++)for (int i=1; i<A; i++)        //把y、z看成定值,累加x方向D[num(i+1,j,k)] += D[num(i,j,k)];for (int i=1; i<=n; i++)    //最后判断是否攻击值大于生命值if (D[i]>s[i])return true;return false;
}
int main() {scanf("%d%d%d%d", &A, &B, &C, &m);n = A*B*C;for (int i=1; i<=n; i++) scanf("%d", &s[i]);  //读生命值for (int i=1; i<=m; i++)                      //读每次攻击的范围,用坐标表示scanf("%d%d%d%d%d%d%d",&x1[i],&x2[i],&y1[i],&y2[i],&z1[i],&z2[i],&d[i]);int L = 1,R = m;      //经典的二分写法while (L<R) {     //对m进行二分,找到临界值。总共只循环了log(m)次int mid = (L+R)>>1;if (check(mid)) R = mid;else L = mid+1;}printf("%d\n", R);  //打印临界值return 0;
}

4. 差分习题

一维差分:poj 3263;hdu 6273,1121;洛谷P3406,P3948,P4552
二维差分:洛谷P3397,hdu 6514
三维差分:蓝桥杯A组2018省赛“三体攻击”

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.rhkb.cn/news/21883.html

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

MiniGPT4,开源了

点击“开发者技术前线”&#xff0c;选择“星标” 让一部分开发者看到未来 量子位 | 公众号 QbitAI GPT-4识图功能迟迟不开放&#xff0c;终于有人忍不住自己动手做了一个。 MiniGPT-4来了&#xff0c;Demo开放在线可玩。 传一张海鲜大餐照片上去&#xff0c;就能直接获得菜谱。…

不愧是微软出品的工具,逆天!

上一篇&#xff1a;逆向了一款涉黄APP&#xff0c;发现了她们的小秘密... 大家好&#xff0c;今天分享一些微软出品的实用小工具&#xff0c;希望对大家有所帮助。 原文链接&#xff1a;https://www.pconline.com.cn/win11/1501/15013664.html 系统增强工具PowerToys 下载地址&…

人工智能AI如何工作及使用

chatgpt聊天软件是一款非常好玩的智能聊天软件&#xff0c;如果你觉得生活非常无趣&#xff0c;或者没有人能诉说烦恼&#xff0c;那么这款软件一定非常适合你。 小凡AI是一款专业的智能助手&#xff0c;可以帮助您快速、高效地处理各种工作任务。它包含强大的语音识别和自然语…

老胡的周刊(第094期)

老胡的信息周刊[1]&#xff0c;记录这周我看到的有价值的信息&#xff0c;主要针对计算机领域&#xff0c;内容主题极大程度被我个人喜好主导。这个项目核心目的在于记录让自己有印象的信息做一个留存以及共享。 &#x1f3af; 项目 qrbtf[2] 艺术二维码生成器&#xff1a; qrb…

两则靠谱的AI招聘信息;长文档阅读的辅助总结神器 Obsidian Copliot;LLM 应用开发全栈指南;重写人工智能时代的创业手册 | ShowMeAI日报

&#x1f440;日报&周刊合集 | &#x1f3a1;生产力工具与行业应用大全 | &#x1f9e1; 点赞关注评论拜托啦&#xff01; &#x1f916; 两则靠谱的AI招聘信息&#xff1a;奇绩创坛 & Copilot Hub 6月14日&#xff0c;奇绩创坛在「奇绩大模型日报体验群」发布招聘信息…

比OpenAI更快一步,最新开源的MiniGPT-4模型可让开发者提前感受GPT-4识图能力!...

整理 | 屠敏 出品 | CSDN&#xff08;ID&#xff1a;CSDNnews&#xff09; 迄今为止&#xff0c;GPT-4 凭借多模态能力已经成为 AI 领域备受关注的大模型&#xff0c;不过值得注意的是&#xff0c;OpenAI 在推出 GPT-4 时虽然引入了对图像理解的能力&#xff0c;但并没有在除了…

谷歌Bard大升级:支持中文,识图功能上线

出品 | OSC开源社区&#xff08;ID&#xff1a;oschina2013) 谷歌对话式 AI 产品 Bard 昨日发布了重要更新&#xff0c;现在已支持更多国家 / 地区和更多语言&#xff08;包括中文&#xff09;。 此外还添加了 Google Lens 功能 —— 可在 prompt 中使用图像&#xff0c;以及新…

ChatGPT类产品和技术的产生会带来哪些影响?

2023年3月15日&#xff0c;GPT-4的发布再次引爆互联网&#xff0c;原有的自然语言理解、推理和对话能力继续增强&#xff0c;更引入了识图等多模态识别功能&#xff0c;有研究认为可以将其视为“通用性人工智能”的初步阶段。在国内&#xff0c;百度同类产品“文心一言“的发布…

基于GPT-4的 IDEA 神仙插件,无需魔法,亲测好用!

近日&#xff0c;Intellij IDEA的插件商店&#xff0c;悄然上线了一个新的插件——Bito&#xff0c;据说可以基于GPT-4和ChatGPT来写代码。短短几天&#xff0c;已经有50多K的下载量了。 我帮大家试用了一下&#xff0c;亲测好用&#xff01; 根据插件介绍显示&#xff0c;Bito…

ChatGPT大浪潮下,AIGC已经开始改造时尚行业了

编辑 | 机器之心 点击下方卡片&#xff0c;关注“自动驾驶之心”公众号 ADAS巨卷干货&#xff0c;即可获取 点击进入→自动驾驶之心【AIGC】技术交流群 AIGC 这股风&#xff0c;吹到了时尚行业&#xff0c;会带来哪些生产力革新&#xff1f; 上线五天&#xff0c;用户破百万&am…

硅谷银行一夜倒闭,海量创业公司遭殃,工资房租统统拿不出

金磊 发自 凹非寺量子位 | 公众号 QbitAI 一夜之间&#xff0c;硅谷银行倒闭了。 这家最受科技和生命科学初创公司青睐的金融机构&#xff0c;就这么被美国联邦存款保险公司&#xff08;FDIC&#xff09;宣判了“死刑”。 事件影响之大&#xff0c;CNBC甚至这样评价&#xff1a…

让我们一起来看看可爱的猫咪吧

我想喜欢小猫咪的人&#xff0c;一定非常可爱和温柔吧 前言 这个视频中的小猫咪贼可爱&#xff0c;然后下面的那给进度条是只小猫咪走来走去的。 然后我就想可以拿进度条做点事情&#xff0c;一开始想搜一搜借鉴一下&#xff0c;但是根本没有这种高度自定义的。唉 经历 互联…

编写猫咪相册应用 HTML

文章目录 1. 标题元素标签2. p元素用于在网站上创建一段文本3. 注释4. 页面主要部分标识标签5. 通过使用img元素来为你的网站添加图片6. 使用锚点元素(a)链接到另一个页面7. 使用 section 元素将照片内容与未来的内容分开8. 无序列表(ul)元素&#xff0c;列表项(li)元素在列表中…

ChatGPT|一文读懂GPT-4!

前言 大家好&#xff0c;今天早上一早醒来&#xff0c;发现各大科技圈公众号平台开始刷屏OpenAI发布的新模型GPT4.0&#xff0c;看这个版本号就已经知道又是一大波特性的更新。 于是立马起来开始学习&#xff01; GPT-4 发布视频&#xff08;2023.03.15&#xff09; www.youtub…

李彦宏谈文心一言:市场反馈符合预期;OpenAI CEO 承认害怕 ChatGPT;Twitter 将开源推荐算法源码|极客头条

「极客头条」—— 技术人员的新闻圈&#xff01; CSDN 的读者朋友们早上好哇&#xff0c;「极客头条」来啦&#xff0c;快来看今天都有哪些值得我们技术人关注的重要新闻吧。 整理 | 梦依丹 出品 | CSDN&#xff08;ID&#xff1a;CSDNnews&#xff09; 一分钟速览新闻点&…

ChatGPT 拿测试 offer ?!

前段时间&#xff0c;全网都在说GPT&#xff0c;听说GPT能写代码、写用例、写算法、写论文、写策划方案、写日报周报新闻稿、种草笔记、视频脚本、作诗作词作曲、处理 Excel 。 心想&#xff1a;这也太厉害了吧&#xff01;都能帮忙写代码和写用例了&#xff0c;我是不是要被取…

读脑术!由大脑信号构建高清视频的方法实现啦,Stable Dinfusion还能这么用

夕小瑶科技说 分享 来源 | 量子位 作者 | 金磊 现在&#xff0c;AI可以把人类脑中的信息&#xff0c;用高清视频展示出来了&#xff01; 例如你坐在副驾所欣赏到的沿途美景信息&#xff0c;AI分分钟给重建了出来&#xff1a; 看到过的水中的鱼儿、草原上的马儿&#xff0c;也…

人工智能之深度学习常见应用方向你都了解吗?(文末福利)

本文导读 从零带你了解深度学习常见的7大应用方向&#xff0c;包括&#xff1a;数字识别、图像识别、图像分类、目标检测、人脸识别、文本分类、聊天机器人。 1. 数字识别 数字识别是计算机从纸质文档、照片或其他来源接收、理解并识别可读的数字的能力&#xff0c;目前比较受…

GPT-4“王炸”发布,背后的这些问题你想到了吗?

今天GPT-4发布&#xff0c;看了一下&#xff0c;主要有这几个方面的飞跃式提升&#xff1a; 强大的识图能力&#xff1b;文字输入限制提升至 2.5 万字&#xff1b;回答准确性显著提高&#xff1b;能够生成歌词、创意文本&#xff0c;实现风格变化。 除此之外&#xff0c;GPT-…