二维前缀和

---

前缀和&差分

很简单的前置姿势，用于处理区间中的数全部加或减某个数，以及询问区间和

前缀和利用$O(n)$预处理，然后通过差分$O(1)$得出区间和

• [l,r]区间全部+q

a[l]+=q, a[r+1]-=q;
...
for(int i=1;i<=n;i++){
    sum[i]=sum[i-1]+a[i];
    //省空间直接用a：a[i]+=a[i-1];
}

• 求[l,r]区间和

ans=sum[r]-sum[l-1];
//a[r]-a[l-1]

二维前缀和

Q：给定一个n*m大小的矩阵A，有若干次操作和询问，操作是以(x1,y1)为左上角坐标和(x2,y2)为右下角坐标的子矩阵的所有元素加上或减去q，并询问该二维区间的所有元素和

对于这样一个问题，可以使用二维前缀和，它主要应用了容斥原理，直接看代码吧

• 预处理（4步操作）

a[x1][y1]+=q;
a[x2][y2]+=q;
a[x1][y2+1]-=q;
a[x2+1][y1]-=q;
...
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];
    }
}

• 求区间和（容斥原理）

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