6.差分（快速区间 / 子矩阵更新）
核心思想
差分是前缀和的逆运算，通过预处理差分数组，将 “区间加 C” 从 O (n) 优化为 O (1)，最终通过前缀和还原原数组。
1. 一维差分
定义
- 原数组
a[1..n]，差分数组b[1..n]，满足a[i] = b[1] + b[2] + ... + b[i]（a 是 b 的前缀和）； - 区间更新公式：给
a[l..r]加 C →b[l] += C，b[r+1] -= C（若 r+1>n 则忽略b[r+1]）； - 初始化：原数组非零时，可视为 “给每个位置 i 的区间 (i,i) 加 a [i]”。
代码模板（含应用）
#include <cstdio>
using namespace std;const int N = 1e5 + 10;
int a[N], b[N];//原数组a[N],差分数组b[N]// 给区间[l..r]加C
void insert(int l, int r, int c)
{b[l] += c;if (r + 1 <= N) b[r+1] -= c;
}int main()
{int n, m;cin>>n>>m;// 初始化差分数组（原数组a非零）for(int i = 1; i <= n; i++) {cin >> a[i];b[i] = a[i] - a[i-1];}// 处理m次区间更新while (m--) {int l, r, c;cin>>l>>r>>c;insert(l, r, c);}// 求前缀和还原原数组for(int i = 1; i <= n; i++) {a[i] = a[i-1] + b[i];cout << a[i] << ' ';}cout << endl;return 0;
}
2. 二维差分（子矩阵更新）
定义
- 原矩阵
a[1..n][1..m]，差分矩阵b[1..n][1..m]，满足a是b的二维前缀和； - 子矩阵更新公式：给
a[x1..x2][y1..y2]加 C →b[x1][y1] += C，b[x2+1][y1] -= C，b[x1][y2+1] -= C，b[x2+1][y2+1] += C； - 初始化：原矩阵非零时，视为 “给每个位置 (i,j) 的子矩阵 (i,j,i,j) 加 a [i][j]”。
\[\begin{cases}
b_{x_{1},y_{1}} += C\\
b_{x_{2}+1,y_{1}} -= C\\
b_{x_{1},y_{2}+1} -= C\\
b_{x_{2}+1,y_{2}+1} += C
\end{cases}
\]
代码模板（含应用）
#include <cstdio>
using namespace std;const int N = 1e3 + 10;
int a[N][N], b[N][N];// 给子矩阵(x1,y1)-(x2,y2)加C
void insert(int x1, int y1, int x2, int y2, int c)
{b[x1][y1] += c;b[x2+1][y1] -= c;b[x1][y2+1] -= c;b[x2+1][y2+1] += c;
}int main()
{int n, m, q;scanf("%d%d%d", &n, &m, &q);// 初始化差分矩阵（原矩阵a非零）for (int i = 1; i <= n; i++){for (int j = 1; j <= m; j++){scanf("%d", &a[i][j]);insert(i, j, i, j, a[i][j]);}}// 处理q次子矩阵更新while (q--) {int x1, y1, x2, y2, c;scanf("%d%d%d%d%d", &x1, &y1, &x2, &y2, &c);insert(x1, y1, x2, y2, c);}// 求二维前缀和还原原矩阵for (int i = 1; i <= n; i++) {for (int j = 1; j <= m; j++) {b[i][j] += b[i-1][j] + b[i][j-1] - b[i-1][j-1];printf("%d ", b[i][j]);}printf("\n");}return 0;
}