差分可以看作是前缀和的逆运算，前缀和可以帮我们快速得到某个区间的和，而差分就是我们将原数组看作是一个前缀和数组（q[]）我们去构造一个差分数组（c[]）

一维差分

使存在如下关系：

q[i] = c[1] + c[2] + c[3] +.....+ c[i]

-> q[i] = q[i - 1] + c[i]

-> c[i] = q[i] - q[i - 1]

eg: q = {2, 3, 6, 1, 7}，下标从1开始方便讲解

按照上述规律我们可以构造出c = {2, 1, 3, -5, 6}

那么差分到底有什么用呢？

假设有这么一个场景我们现在给定一个区间[l, r]现在我们需要对原数组的[l, r]的数据都加上5，最直接的想法就是我们从l开始遍历到r然后给每个数+5，时间复杂度是O（n），如果我们现在需要执行m次如上操作就是O（n*m）这个开销不算太好。这时我们的差分就堂堂登场了，还记得差分的定义吗，原数组就是差分数组的前缀和，如果我们令c[l] + 5就是令q[l....]+5(因为l后的元素都会+c[l])，令c[r + 1] - 5就是令q[r+1....] - 5(因为r+1后的元素都会+c[r+1])，这两个一叠加就变成了q[l...r]+5了，我们只需要O（1）就能完成修改，执行m次的开销也只花费O（m），这有了极大的提升对于原来的暴力法。

代码实现：

int n, m;//n个数，m次修改
int q[n + 1], c[n + 1];void change(int l, int r, int value) {c[l] += value;if(r + 1 <= n) c[r + 1] -= value;
}int main() {for(int i = 1; i <= n; i++) c[i] = q[i] - q[i - 1];for(int i = 1; i <= m; i++) {int l, r, value;cin >> l >> r >> value;change(l, r, value);}//得到经过m次修改后的数组for(int i = 1; i <= n; i++) {q[i] = q[i - 1] + c[i];}
}

二维差分

二维差分的作用与一维差分是一样的，都是用来快速修改某个范围的数据，不过是从[l, r]，变成了左上顶点(x1, y1) -> 右下顶点(x2, y2)。

我们还是先来确定一下原数组和差分数组的关系，q[x] [y]等于c[1] [1]到c[x] [y]（左上顶点和右下顶点框出的矩阵）内的数据和：

q[x] [y] = c[1] [1] + ... + c[1] [y] + c[2] [1] + ...+c[2] [y] + ... + c[x] [1] +...+ c[x] [y];

我们可以画图来展现一下c数组：

 

通过上述规律我们可以知道：

红色：q[x-1] [y-1]

蓝色：q[x] [y-1]

深蓝色：q[x-1] [y]

绿色：c[x] [y]

我们可以得到这样的推论：q[x] [y] = q[x - 1] [y] + q[x] [ y-1] + c[x] [y] - q[x - 1] [y - 1]，

移项后：c[x] [y] = q[x] [y] + q[x - 1] [y - 1] - q[x - 1] [y] - q[x] [y -1]

这样我们就可以通过原数组q来构造差分数组c

如果我们希望(x, y) 到 (x2, y2)范围内的数据都改变value。

 

参照一维差分的规律我们可以想到就是c[x] [y] +value,会使橙色范围的q+value，我们希望紫色范围的不发生改变，所以c[x2+1] [y] - value、c[x] [y2 + 1] - value, 但这样导致粉色区域多减了一次还需要加回来c[x2+1] [y2+1] + value,这样就完成了修改

代码实现：

int q[n+1][m+1], c[n+1][m+1];//下标都还从1开始void change(int x1, int y1, int x2, int y2, int value) {c[x1][y1] += value;//注意边界判断这里就不写了c[x2 + 1][y1] -= value;c[x1][y2 + 1] -= value;c[x2 + 1][y2 + 1] += value;
}int main() {//num次修改for(int i = 1; i <= num; i++) {int x1, y1, x2, y2, value;cin >> x1 >> y1 >> x2 >> y2 >> value;change(x1, y1, x2, y2, value);}//得到修改后的数据for(int i = 1; i <= n; i++) for(int j = 1; j <= m; j++) q[i][j] = q[i - 1][j] + q[i][j - 1] + c[i][j] - q[i - 1][j - 1];
}