首页 > 其他 > 详细

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

时间:2020-10-03 23:58:30      阅读:37      评论:0      收藏:0      [点我收藏+]
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

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!