前缀和

前缀和

一维：

构建前缀数组：

for(int i=1;i<=n;++i)
  a[i]+=a[i-1];

应用场景：

①求 \(a[1]～a[i]\)的累加和

ans=a[i];

②求\(a[i]～a[j](j>=i)\)的累加和

ans=a[j]-a[i-1];

二维：

构建前缀数组：

for(int i=1;i<=n;++i)
    for(int j=1;j<=m;++j)
        a[i][j]+=a[i-1][j]+a[i][j-1]-a[i-1][j-1];

应用场景：

求\((x_1<=i<=x_2,y_1<=j<=y_2)\)范围内的\(c[i][j]\)之和

ans=a[x2][y2]+a[x1-1][y1-1]-a[x1-1][y2]-a[x2][y1-1];