1.一维差分(实质:前缀和的逆运算)
给区间[l, r]
中的每个数加上c:B[l] += c, B[r + 1] -= c
上述操作可以免去构造一个新数组,可以直接给差分赋值
2.二维差分
给以(x1, y1)
为左上角,(x2, y2)
为右下角的子矩阵中的所有元素加上C:
S[x1, y1] += c, S[x2 + 1, y1] -= c, S[x1, y2 + 1] -= c, S[x2 + 1, y2 + 1] += c
给区间[l, r]
中的每个数加上c:B[l] += c, B[r + 1] -= c
给以(x1, y1)
为左上角,(x2, y2)
为右下角的子矩阵中的所有元素加上C:
S[x1, y1] += c, S[x2 + 1, y1] -= c, S[x1, y2 + 1] -= c, S[x2 + 1, y2 + 1] += c