OI

【模板】前缀和、差分

前缀和进阶
各种奇怪题目的优化有奇效！

前缀和算法可以在常数时间复杂度内计算给定区间i~j的和，而从头扫一遍的复杂度为O(n)；而二维前缀和则可以在常数时间内计算(x1,y1)到(x2,y2)矩阵内的和，而从头扫一遍为O(n^2)！！

一维前缀和

给定n个数，m组询问，求i~j区间的和

上次讲用线段树做，但前缀和更方便一些。

设s[i]表示第一个数加到第i个数的和，则sum(i,j)=s[j]-s[i-1]

而预处理又可以随读入一起完成，效率就很高了。

1
2
3
4
5
6
7
8
scanf("%d",&n);
for(i=1;i<=n;i++){
    scanf("%d",&a[i]);
    s[i]=s[i-1]+a[i];
}
int sum(int i,int j){
    return s[j]-s[i-1];
}

二维前缀和

由一维可以推广到二维：计算从(x1,y1)到(x2,y2)的矩阵的和。

这个优化就更加明显了，直接从O(n^2)降到了O(1)。

设s[i][j]表示从(0,0)到(i,j)的矩阵的和

由容斥原理，sum(x1,y1,x2,y2)=s[x2][y2]-s[x1][y2-1]-s[x2-1][y1]+s[x1-1][y1-1]

1
2
3
4
5
6
7
8
9
scanf("%d",&n);
for(i=1;i<=n;i++)
  for(j=1;j<=n;j++){
    scanf("%d",&a[i][j]);
    s[i][j]=s[i-1][j]+s[i][j-1]-s[i-1][j-1]+a[i][j];
  }    
int sum(int x1,int y1,int x2,int y2){
    return s[x2][y2]+s[x1-1][y1-1]-s[x1-1][y2]-s[x2][y1-1];
}


就这样，又方便又快