如何实现6.差分（快速区间子矩阵更新）的高效算法？
摘要：6.差分（快速区间子矩阵更新） 核心思想 差分是前缀和的逆运算，通过预处理差分数组，将 “区间加 C” 从 O (n) 优化为 O (1)，最终通过前缀和还原原数组。 1. 一维差分 定义 原数组a[1..n]，差分数组b[1..n]
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;
}