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++;再执行第一类的基本操作。
若为第一类：
左下角对应的则是蓝色小正方形的中心，对于此类问题，直接采取以上代码即可求二维差分。
然后来个基于差分的前缀和即可。
求一次前缀和可得原数；求两次前缀和才是真正的和。
1 for(int i = 0 ; i <= sz ; i++){ 2 for(int j = 0 ; j <= sz ; j++){ 3 if(i >= 1) M[i][j] += M[i - 1][j]; 4 if(j >= 1) M[i][j] += M[i][j - 1]; 5 if(i >= 1 && j >= 1) M[i][j] -= M[i-1][j-1]; 6 } 7 }
原文：https://www.cnblogs.com/ecustlegendn324/p/13765831.html