一维差分#

• 核心思想：把「区间 [L,R] 全部元素 +k」
• 时间优化：O(R−L+1) 降到 O(1)
• 差分数组 f 是原数组 a 的相邻元素之差序列

1. 差分数组两种构造方式

1
1.
2
f[i]=a[i]-a[i-1];//a[0]=0;

1
2.
2
 f[i]+=a[i];
3
 f[i+1]-=a[i];

2. 区间修改（m次）

1
f[l]+=k;
2
f[r+1]-=k;

3. 还原数组(对f进行前缀和)

1
a[i]=f[1]+f[2]+...+f[i]；

二维差分#

• 核心思想：把「子矩阵 (x1,y1)~(x2,y2) 全部元素 +k」
• 时间优化 O(nm) 降到 O(1)

1. 性质 在差分矩阵 f 中，给单点 (x,y) 加 k，会影响原矩阵中以 (x,y) 为左上角、(n,m) 为右下角的整个子矩阵全部 +k。
2. 子矩阵+k的四角操作

1
 f[x1][y1]  += k；
2
 f[x1][y2+1] -= k；
3
 f[x2+1][y1] -= k；
4
 f[x2+1][y2+1] += k；

3. 还原原矩阵 对 f 做二维前缀和；前缀和