前缀和
前缀和
一维：
构建前缀数组：
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];