呼市建设委员会网站每天三分钟新闻天下事

2025 - 03 - 08 - 第 71 篇
Author: 郑龙浩 / 仟濹
【二维差分】

前缀和与差分 - 我的博客

一维前缀和
【算法 C/C++】一维前缀和
一维差分
【算法 C/C++】一维差分
二维前缀和
【算法 C/C++】二维前缀和
二维差分
【算法 C/C++】二维差分

差分(二维)

回顾一下一维差分的用法，通过打标记，将前面的标记带到后边去

1 大体思路 | 一些区间加某数的最终结果

二维差分和一维差分有些许的相同，都是

• 进行差分标记 - 记录区间边界以及在边界位置使用某种方法记录增量
• 然后进行前缀和计算，得出每个元素的的增量为多少
• 将原数组与增量差分数组进行一对一的结合，得出增量以后的结果

2 二维差分原理

前面学了 一维前缀和，一维差分，二维前缀和，已经有了基础，二维差分原理就不写那么具体了。

总之还是确定边界，即如何进行二维差分标记，之前一维差分标记是每个区间有两个标记。

假设 {x1, y1}{x2, y2} + value

d[x1][y1] += value;
d[x2 + 1][y1] -= value;
d[x1][y2 + 1] -= value;
d[x2 - 1][y2 - 1] += value;

四个标记点的意义

• 起点标记 d[x1][y1] += value
  从该点开始影响整个后续区域
• 右界限制 d[x1][y2+1] -= value
  消除右侧超出 y2 列的增量
• 下界限制 d[x2+1][y1] -= value
  消除下方超出 x2 行的增量
• 交叉修正 d[x2+1][y2+1] += value
  补回右侧和下侧重复抵消的部分

3 例题

题目

有一个 3*4 的矩阵 arr[N][M]

{1, 5, 6, 8,9, 6, 7, 3,5, 3, 2, 4}

求 (0, 0) 到 (2, 1) +3
求 (1, 1) 到 (2, 2) -1

//答案应为
4  8  6  8
12 8  6  3
8  5  1  4

代码:

// Author: 郑龙浩/仟濹
// Time: 2025-03-08
// [二维差分 二维前缀和]
// **题目**
// 有一个 3*4 的矩阵 `arr[N][M]`
// ```cpp
// {1, 5, 6, 8,
//  9, 6, 7, 3,
//  5, 3, 2, 4}
// ```
// 求  `(0, 0)` 到 `(2, 1)` `+3`
// 求  `(1, 1)` 到 `(2, 2)` `-1`
// ```cpp
// //答案应为
// 4  8  6  8
// 12 8  6  3
// 8  5  1  4
// ```
#include <bits/stdc++.h>
using namespace std;
#define N 3
#define M 4
int arr[N][M] = {1, 5, 6, 8,9, 6, 7, 3,5, 3, 2, 4};
int d[N + 1][M + 1] = {0}; // 增量差分数组// 二维差分数组 - 计算区间边界，并进行差分标记
void d_add(int x1, int y1, int x2, int y2, int value);
// 打印二维数组
void myPrint(int arr[][M]);
int main( void ){// 差分数组 - 计算区间边界，并进行标记d_add(0, 0, 2, 1, 3);d_add(1, 1, 2, 2, -1);// 进行二维前缀和操作// 前缀和以后，就得出了二维矩阵中每个元素的增量应该为多少// 计算列的前缀和for (int i = 1; i <= N; i++) d[i][0] += d[i - 1][0];// 计算行的前缀和for (int i = 1; i <= M; i++) d[0][i] += d[0][i - 1];// 计算全部前缀和for (int i = 1; i < N; i++)for ( int j = 1; j < M; j ++ ){d[i][j] = d[i - 1][j] + d[i][j - 1] + d[i][j] - d[i - 1][j - 1];}// 将两个数组中的元素尽心合并// arr数组中的每个元素加上增量for (int i = 0; i < N; i++)for (int j = 0; j < M; j++)arr[i][j] += d[i][j];// 打印数组 - 打印最终结果myPrint( arr );return 0;
}// 二维差分数组 - 计算区间边界，并进行差分标记
void d_add(int x1, int y1, int x2, int y2, int value){d[x1][y1] += value;d[x2 + 1][y1] -= value;d[x1][y2 + 1] -= value;d[x2 + 1][y2 + 1] += value; // 将多减去的部分加上
}// 打印二维数组
void myPrint(int arr[][M]){for (int i = 0; i < N; i++){for (int j = 0; j < M; j++)printf ("%-3d", arr[i][j]);cout << endl;}
}