前缀和

目的：求原数组中某段数的和（O（1））

具体做法：做一个预处理，定义一个新数组储存原数组前i个数的和

一维前缀和：

预处理：

1
2
int sum[N],a[N];
for(int i=1;i<=n;i++)sum[i]=sum[i-1]+a[i];

查找：（求l~r之间的数）

1
num=sum[r]-sum[l-1];

二维前缀和：(当成方格形)

预处理：

1
2
3
4
int sum[N][M],a[N][M];
for(int i=1;i<=n;i++)
    for(int j=1;j<=m;j++)
        sum[i][j]=sum[i-1][j-1]-sum[i-1][j]-sum[i][j-1]+a[i][j];

查找：（求(l1,r1)~(l2,r2)之间的数）

1
num=sum[l2][r2]-sum[l2][r1-1]-sum[l1-1][r2]+sum[l1][r1];

高维前缀和：（类比）