关于二维差分和二维前缀和的注意事项

int sz;
for(int i = 1 ; i <= n ; i++){
        scanf("%d%d%d%d",&X1,&Y1,&X2,&Y2);
        //X1++;Y1++;
        M[X1][Y1]++;
        if(Y2 + 1 <= sz)    M[X1][Y2 + 1]--;
        if(X2 + 1 <= sz)    M[X2 + 1][Y1]--;
        if(X2 + 1 <= sz && Y2 + 1 <= sz)    M[X2 + 1][Y2 + 1]++;
    }

在边界处需确认，包括 X1 - 1等类似情况，需要判断与0的关系。

其次，上面代码注释的那一行是二维差分的细节关键。

当题目给定1*1小正方形的两个坐标，直接使用二维差分。

若题目给定的是两条细线所交的边界点，实则矩形的长宽会各减少1，因此需要将靠近原点的坐标x, y分别++。

上图中，若为第二类：

　　实际面积为3*3的粉色区域，最后若需求得面积，则x1++;y1++;再执行第一类的基本操作。

若为第一类：

　　左下角对应的则是蓝色小正方形的中心，对于此类问题，直接采取以上代码即可求二维差分。

然后来个基于差分的前缀和即可。

求一次前缀和可得原数；求两次前缀和才是真正的和。

for(int i = 0 ; i <= sz ; i++){
    for(int j = 0 ; j <= sz ; j++){
        if(i >= 1)    M[i][j] += M[i - 1][j];
        if(j >= 1)    M[i][j] += M[i][j - 1];
        if(i >= 1 && j >= 1)    M[i][j] -= M[i-1][j-1];
    }
}