基础算法：差分

一维差分

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

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

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

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

2. 区间修改（m次）

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

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

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的四角操作

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

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

关于前缀和笔记发布在上一篇文章