1维2维3维前缀和

应用

前缀和主要应用于对区间内每个数进行加或减操作时，如果遍历区间进行操作，时间复杂度较高，在数据量大时无法AC，如果对差分数组进行操作的话，可以把时间复杂度降为O(1)，可以AC

下面设b[]数组为前缀和数组，s[]数组为原数组

一维前缀和

• 构造差分数组：$b[i]=s[i]-s[i-1]$

• 求原数组（前缀和操作）：$s[i]=b[i]+s[i-1]$

• 给 l 到 r 区间加 c ，对差分数组的插入操作：

  b[l] += c

  b[r+1] -= c

二维前缀和

• 构造差分数组：$b[i][j]=s[i][j]-s[i-1][j]-s[i][j-1]+s[i-1][j-1]$

• 求原数组（前缀和操作）：$s[i][j]=b[i][j]+s[i-1][j]+s[i][j-1]-s[i-1][j-1]$

• 给(x1,y1)到(x2,y2) 加 c ,对差分数组的插入操作：

  $b[x1][y1]+=c$

  $b[x2+1][y1]-=c$

  $b[x1][y2+1]-=c$

  $b[x2+1][y2+1]+=c$

三维前缀和

• S(x,y,z) = b(x,y,z) + S(x-1,y,z) + S(x,y-1,z) - S(x-1,y-1,z) + S(x,y,z-1) - S(x-1,y,z-1) - S(x,y-1,z-1) + S(x-1,y-1,z-1)​

• 由上式 可得 b(x,y,z) 计算公式，此处省略

• 给(x1,y1,z1) 到 (x2,y2,z2) 加 h，对差分数组的插入操作 ：

  int get(int i,int j,int k)
  {
      return ((i-1)*B+(j-1))*C+(k-1)+1;
  }
  void insert(int x1,int x2,int y1,int y2,int z1,int z2,int c)
  {
      b[get(x1,    y1,    z1)]   += c;
      b[get(x1,    y1,    z2+1)] -= c;
      b[get(x1,    y2+1,  z1)]   -= c;
      b[get(x1,    y2+1,  z2+1)] += c;
      b[get(x2+1,  y1,    z1)]   -= c;
      b[get(x2+1,  y1,    z2+1)] += c;
      b[get(x2+1,  y2+1,  z1)]   += c;
      b[get(x2+1,  y2+1,  z2+1)] -= c;
  }
  

三维前缀和例题