如何实现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]”。