二维累积和 | 动画算法与数据结构

符号

数据
叠加的矩形的数量 A

添加矩形
与左上角的点和右下角的点的相对应的元素值加 1 A[x1][y1]++
A[x2][y2]++
与左下角的点和右上角的点相对应的元素值减 1 A[x1][y2]--
A[x2][y1]--
扫描水平方向
与前一个元素相加 A[x][y] ← A[x][y] + A[x-1][y]
扫描垂直方向
与前一个元素相加 A[x][y] ← A[x][y] + A[x][y-1]

动画

添加矩形
二维累积和 | 添加矩形

扫描水平方向
二维累积和 | 扫描水平方向

扫描垂直方向
二维累积和 | 扫描垂直方向