约 10 分钟
对子矩阵 (x1,y1)-(x2,y2) 整体加 v,用二维差分四角打标记:d[x1][y1]+=v; d[x2+1][y1]-=v; d[x1][y2+1]-=v; d[x2+1][y2+1]+=v;,最后对 d 做二维前缀和还原。多次矩阵加时高效。
d[x1][y1]+=v; d[x2+1][y1]-=v; d[x1][y2+1]-=v; d[x2+1][y2+1]+=v;
二维差分一次矩阵修改要打几个标记?
登录 后可看答案