基础算法--前缀和与差分

一、前缀和与差分的基本概念

1.什么是前缀和

现有一个长度为n的数组a[0]~a[n-1]，它的前缀和sum[i]=a[0]~a[i]的加和，如:sum[0]=a[0]，sum[1]=a[0]+a[1]，sum[2]=a[0]+a[1]+a[2]，等等以此类推。利用递推，求出所有的前缀和的时间复杂度仅为O(n)，小于用暴力枚举的时间复杂度O(n^2)。

利用前缀和可以快速地求出数组中某一段区间a[i]~a[j]的值的总和:a[i]+a[i+1]+....+a[j-1]+a[j]=sum[j]-sum[i-1]，时间复杂度由暴力枚举的O(n)优化到了O(1)。

2.什么是差分---差分是前缀和的一个应用

差分具体应用于对区间的修改与询问问题。比如给定一个数组，对这个数组中的某个特定区间中的元素进行集体加或减。若使用暴力枚举--时间复杂度会过大，所以我们引入了差分的概念。

二、一维差分与二维差分

1.一维差分

给定一个一维数组a[]，现在要对这个数组中某段区间的元素进行m次同时加某个值或者同时减某个值的操作，若用暴力枚举法，时间复杂度为O(mn)，若用差分法，则可以将时间复杂度优化至O(m+n)，大幅提高效率。

在差分法当中，用到了两个数组---原数组a[]和差分数组D[]，其中D[i]=a[i]-a[i-1]，由此可联想到a[i]=a[i]-a[i-1]+a[i-1]-a[i-2]+....-a[2]+a[2]-a[1]+a[1]-a[0]=D[i]+D[i-1]+....+D[1]。

那么，如何使数组区间[L,R]中的每个元素同加或者同减一个d的value呢？令D[L]+=d并且D[R+1]-=d即可。

例题：hdu-1556 -- 杭电yyds，NEU好好学学人家

#include<bits/stdc++.h>
using namespace std;
const int N = 100010;
int a[N],D[N];        //a[i]为气球涂色区间测试数量,D[i]是差分数组
int main()
{
  int n,L,R;
  while(cin>>n)   //输入N=0时输入结束
  {
    memset(a,0,sizeof(a));
    memset(D,0,sizeof(D));
    for(int i=1;i<=n;i++)
    {
      cin>>L>>R;
      D[L]++;
      D[R-1]--;       //修改区间
    }
  }
  
  for(int i=1;i<=n;i++)
  {
    a[i] = a[i-1] + D[i];
    cout<<a[i];
  }
}

Note:一个小技巧，可以将a[i]=a[i-1]+D[i]直接写成D[i]=D[i-1]+D[i]，用新的D[i]直接覆盖原来的D[i]，可以直接省去一半的空间，这个技巧在二维差分甚至三维差分中都非常的常见，有些阴间的题目会给你非常极限的空间，可以参考 洛谷-P2280。

2.二维差分

如图，差分数组D[i][j]用面积可以形象的表现出来

区间的修改:

在一维数组中，我们用[L,R]来代表区间，而在二维数组中，我们通常用两个点的坐标(x1,y1)(x2,y2)来定义区间，修改操作如图，其实和一维差分有异曲同工之处

上例题：洛谷-P3397

#include<bits/stdc++.h>
using namespace std;
int n,m;
int D[5000][5000];  //差分数组
int a[5000][5000];
int main()
{
  cin>>n>>m;
  while(m--)
  {
    int x1,y1,x2,y2;
    cin>>x1>>y1>>x2>>y2;
    D[x1][y1]++;             //计算差分数组
    D[x2+1][y2+1]++;
    D[x1][y2+1]--;
    D[x2+1][y1]--;
  }
  for(int i=1;i<=n;i++)
  {
    for(int j=1;j<=n;j++)
    {
      a[i][j] = D[i][j] + a[i-1][j] + a[i][j-1] - a[i-1][j-1];
      cout<<a[i][j]<<" ";
    }
    cout<<endl;
  }
  return 0;
}

其中的a[][]都可以换成D[][]，节省一半的空间，道理与一维差分相同。

如果还学有余力，不妨试试 洛谷-P2280，这道题凸显了空间的重要性，下一期准备出这道题的思路题解，和倍增算法与ST表的相关问题