二维静态差分
二维静态差分
二维差分是一维差分在二维平面上的扩展，用于处理矩阵的子矩阵修改问题。
通过二维差分数组，可以将子矩阵修改的时间复杂度从 优化到
。
基本概念
二维差分的核心思想是：
- 构建二维差分数组
，其中
表示相邻格子的差值
- 子矩阵修改转化为差分数组的四个点的修改
- 原矩阵可以通过二维前缀和还原
- 适用于频繁进行子矩阵修改的场景
实现方式
二维差分的实现步骤：
- 构建二维差分数组
- 通过四点修改实现子矩阵增加
- 通过二维前缀和还原原矩阵
- 处理查询操作
基本实现
class Difference2D {
private:
vector<vector<int>> diff;
int m, n;
public:
Difference2D(vector<vector<int>>& matrix) {
m = matrix.size();
n = matrix[0].size();
diff.resize(m + 1, vector<int>(n + 1));
// 构建二维差分数组
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
increment(i, j, i, j, matrix[i][j]);
}
}
}
// 子矩阵[(x1,y1), (x2,y2)]增加val
void increment(int x1, int y1, int x2, int y2, int val) {
diff[x1][y1] += val;
diff[x1][y2 + 1] -= val;
diff[x2 + 1][y1] -= val;
diff[x2 + 1][y2 + 1] += val;
}
// 还原原矩阵
vector<vector<int>> result() {
vector<vector<int>> res(m, vector<int>(n));
// 二维前缀和
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
res[i][j] = diff[i][j];
if (i > 0) res[i][j] += res[i-1][j];
if (j > 0) res[i][j] += res[i][j-1];
if (i > 0 && j > 0) res[i][j] -= res[i-1][j-1];
}
}
return res;
}
};
class Difference2D {
private int[][] diff;
private int m, n;
public Difference2D(int[][] matrix) {
m = matrix.length;
n = matrix[0].length;
diff = new int[m + 1][n + 1];
// 构建二维差分数组
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
increment(i, j, i, j, matrix[i][j]);
}
}
}
// 子矩阵[(x1,y1), (x2,y2)]增加val
public void increment(int x1, int y1, int x2, int y2, int val) {
diff[x1][y1] += val;
diff[x1][y2 + 1] -= val;
diff[x2 + 1][y1] -= val;
diff[x2 + 1][y2 + 1] += val;
}
// 还原原矩阵
public int[][] result() {
int[][] res = new int[m][n];
// 二维前缀和
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
res[i][j] = diff[i][j];
if (i > 0) res[i][j] += res[i-1][j];
if (j > 0) res[i][j] += res[i][j-1];
if (i > 0 && j > 0) res[i][j] -= res[i-1][j-1];
}
}
return res;
}
}
class Difference2D:
def __init__(self, matrix):
self.m = len(matrix)
self.n = len(matrix[0])
self.diff = [[0] * (self.n + 1) for _ in range(self.m + 1)]
# 构建二维差分数组
for i in range(self.m):
for j in range(self.n):
self.increment(i, j, i, j, matrix[i][j])
# 子矩阵[(x1,y1), (x2,y2)]增加val
def increment(self, x1, y1, x2, y2, val):
self.diff[x1][y1] += val
self.diff[x1][y2 + 1] -= val
self.diff[x2 + 1][y1] -= val
self.diff[x2 + 1][y2 + 1] += val
# 还原原矩阵
def result(self):
res = [[0] * self.n for _ in range(self.m)]
# 二维前缀和
for i in range(self.m):
for j in range(self.n):
res[i][j] = self.diff[i][j]
if i > 0: res[i][j] += res[i-1][j]
if j > 0: res[i][j] += res[i][j-1]
if i > 0 and j > 0: res[i][j] -= res[i-1][j-1]
return res
应用场景
二维差分在很多问题中都有应用：
- 图像区域修改
- 地图区域更新
- 矩阵区域增减
- 二维网格修改
- 热力图更新
示例：矩阵区域增加
vector<vector<int>> getModifiedMatrix(vector<vector<int>>& matrix,
vector<vector<int>>& operations) {
Difference2D diff(matrix);
// 执行所有更新操作
for (const auto& op : operations) {
int x1 = op[0], y1 = op[1];
int x2 = op[2], y2 = op[3];
int val = op[4];
diff.increment(x1, y1, x2, y2, val);
}
return diff.result();
}
public int[][] getModifiedMatrix(int[][] matrix, int[][] operations) {
Difference2D diff = new Difference2D(matrix);
// 执行所有更新操作
for (int[] op : operations) {
int x1 = op[0], y1 = op[1];
int x2 = op[2], y2 = op[3];
int val = op[4];
diff.increment(x1, y1, x2, y2, val);
}
return diff.result();
}
def getModifiedMatrix(self, matrix: List[List[int]], operations: List[List[int]]) -> List[List[int]]:
diff = Difference2D(matrix)
# 执行所有更新操作
for x1, y1, x2, y2, val in operations:
diff.increment(x1, y1, x2, y2, val)
return diff.result()
时间复杂度
- 构建差分数组：
- 子矩阵修改：
- 单点查询：
（需要还原原矩阵）
- 空间复杂度：
二维差分 vs 一维差分
优点：
- 支持二维区域修改
- 实现相对简单
- 适用于多个区域修改
缺点：
- 查询需要还原整个矩阵
- 空间复杂度较高
- 不支持动态修改
注意事项
- 差分数组的大小处理
- 子矩阵修改的边界
- 还原时的前缀和计算
- 处理负数和溢出
练习建议
- 实现基本的二维差分
- 解决矩阵修改问题
- 结合实际应用场景
- 尝试动态二维差分
经典例题
牛客代码笔记-牛栋 文章被收录于专栏
汗牛充栋，学海无涯。<br/> 内含算法知识点讲解，以及牛客题库精选例题。<br/> 学习算法，从牛栋开始。
投递旷视等公司10个岗位
查看6道真题和解析
