差分与前缀和互为逆运算。
一维差分用来将子数组每个元素加上c，可以将复杂度由$O(n)$降为$O(1)$。
原数组a、差分数组d必须在前部有0边界，即a[0] = 0、s[0] = 0；
a[1...n]、d[1...n]存储数据。
void add(int l, int r, int c) {
d[l] += c;
d[r+1] -= c;
}
for (int i = 1; i <= n; i++) add(i, i, a[i]);
add(l, r, c);
for (int i = 1; i <= n; i++) d[i] += d[i-1];
二维差分用来将子矩阵每个元素加上c，可以将复杂度由$O(n*m)$降为$O(1)$。
原矩阵a、差分矩阵d必须在前部有0边界，即a[0][0...n] = a[0...n][0] = 0、d[0][0...n] = d[0...n][0] = 0；
a[1…n][1…n]、d[1…n][1…n]存储数据。
void add(int x1, int y1, int x2, int y2, int c) {
d[x1][y1] += c;
d[x2+1][y1] -= c;
d[x1][y2+1] -= c;
d[x2+1][y2+1] += c;
}
for (int i = 1; i <= n; i++)
for (int j = 1; j <= m; j++)
add(i, j, i, j, a[i][j]);
add(x1, y1, x2, y2, c);
for (int i = 1; i <= n; i++)
for (int j = 1; j <= m; j++)
d[i][j] += d[i-1][j] + d[i][j-1] - d[i-1][j-1];