二维差分矩阵
差分矩阵的前缀和就是原矩阵;假设已经有了差分矩阵,我们想要使(x1,y1) (x2,y2)这两个点的所有值+d,那么对于差分矩阵 如果在(x1,y1)处+d,那就是(x1,y1)到右下角都+d了 因为前缀和包含了这个(x1,y1)点值的区域都会+d,那么多的区域就要减去也就是 (x2+1,y1) 位置-d 然后(x1,y2+1)-d 最后重复剪掉的(x2+1,y2+1)
diff[x_1][y_1] +=d
diff[x_1][y_2+1] -=d
diff[x_2+1][y_1] -= d
diff[x_1+1][y_1+1] +=d
那如何构造差分数组?直接默认构造一个全0矩阵,那么每次遍历到一个点(x,y) 他的值是value
那其实就等于使得(x1,y1) (x2,y2) 区域 且x1=x2 y1=y2 ,加上了value,那就可以直接操作差分矩阵
diff[x][y]+=value
diff[x][y+1]-=value
diff[x+1][y]-=value
diff[x+1][y+1]+=value