02.09_二维动态差分（区修单查）
二维动态差分（区修单查）
二维动态差分是二维差分的动态实现，通过二维树状数组维护差分数组，可以在 的时间复杂度内完成子矩阵修改和单点查询操作。
基本概念
二维动态差分的核心思想是：
- 使用二维树状数组维护差分数组
- 子矩阵修改转化为四个点的修改
- 单点查询通过二维前缀和实现
- 适用于子矩阵修改和单点查询交替的场景
实现方式
二维动态差分的关键操作：
- update：修改差分数组某个位置的值
- query：查询差分数组的二维前缀和
- rangeAdd：子矩阵增加操作
- pointQuery：单点查询
基本实现
class DynamicDifference2D {
private:
vector<vector<int>> tree;
int m, n;
int lowbit(int x) {
return x & (-x);
}
void update(int x, int y, int val) {
for (int i = x; i <= m; i += lowbit(i)) {
for (int j = y; j <= n; j += lowbit(j)) {
tree[i][j] += val;
}
}
}
int query(int x, int y) {
int sum = 0;
for (int i = x; i > 0; i -= lowbit(i)) {
for (int j = y; j > 0; j -= lowbit(j)) {
sum += tree[i][j];
}
}
return sum;
}
public:
DynamicDifference2D(int rows, int cols) : m(rows), n(cols) {
tree.resize(m + 1, vector<int>(n + 1));
}
// 子矩阵[(x1,y1), (x2,y2)]增加val
void rangeAdd(int x1, int y1, int x2, int y2, int val) {
update(x1 + 1, y1 + 1, val);
update(x1 + 1, y2 + 2, -val);
update(x2 + 2, y1 + 1, -val);
update(x2 + 2, y2 + 2, val);
}
// 查询位置(x,y)的值
int pointQuery(int x, int y) {
return query(x + 1, y + 1);
}
};
class DynamicDifference2D {
private int[][] tree;
private int m, n;
public DynamicDifference2D(int rows, int cols) {
m = rows;
n = cols;
tree = new int[m + 1][n + 1];
}
private int lowbit(int x) {
return x & (-x);
}
private void update(int x, int y, int val) {
for (int i = x; i <= m; i += lowbit(i)) {
for (int j = y; j <= n; j += lowbit(j)) {
tree[i][j] += val;
}
}
}
private int query(int x, int y) {
int sum = 0;
for (int i = x; i > 0; i -= lowbit(i)) {
for (int j = y; j > 0; j -= lowbit(j)) {
sum += tree[i][j];
}
}
return sum;
}
// 子矩阵[(x1,y1), (x2,y2)]增加val
public void rangeAdd(int x1, int y1, int x2, int y2, int val) {
update(x1 + 1, y1 + 1, val);
update(x1 + 1, y2 + 2, -val);
update(x2 + 2, y1 + 1, -val);
update(x2 + 2, y2 + 2, val);
}
// 查询位置(x,y)的值
public int pointQuery(int x, int y) {
return query(x + 1, y + 1);
}
}
class DynamicDifference2D:
def __init__(self, rows, cols):
self.m = rows
self.n = cols
self.tree = [[0] * (cols + 1) for _ in range(rows + 1)]
def lowbit(self, x):
return x & (-x)
def update(self, x, y, val):
i = x
while i <= self.m:
j = y
while j <= self.n:
self.tree[i][j] += val
j += self.lowbit(j)
i += self.lowbit(i)
def query(self, x, y):
total = 0
i = x
while i > 0:
j = y
while j > 0:
total += self.tree[i][j]
j -= self.lowbit(j)
i -= self.lowbit(i)
return total
# 子矩阵[(x1,y1), (x2,y2)]增加val
def range_add(self, x1, y1, x2, y2, val):
self.update(x1 + 1, y1 + 1, val)
self.update(x1 + 1, y2 + 2, -val)
self.update(x2 + 2, y1 + 1, -val)
self.update(x2 + 2, y2 + 2, val)
# 查询位置(x,y)的值
def point_query(self, x, y):
return self.query(x + 1, y + 1)
应用场景
二维动态差分在很多问题中都有应用：
- 动态图像处理
- 实时地图更新
- 在线矩阵修改
- 动态热力图
- 实时区域统计
示例：矩阵区域增加
class Solution {
private:
DynamicDifference2D* dd;
public:
vector<vector<int>> getModifiedMatrix(vector<vector<int>>& matrix,
vector<vector<int>>& operations) {
int m = matrix.size(), n = matrix[0].size();
dd = new DynamicDifference2D(m, n);
// 执行所有更新操作
for (const auto& op : operations) {
int x1 = op[0], y1 = op[1];
int x2 = op[2], y2 = op[3];
int val = op[4];
dd->rangeAdd(x1, y1, x2, y2, val);
}
// 查询每个位置的值
vector<vector<int>> result(m, vector<int>(n));
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
result[i][j] = dd->pointQuery(i, j);
}
}
return result;
}
};
class Solution {
private DynamicDifference2D dd;
public int[][] getModifiedMatrix(int[][] matrix, int[][] operations) {
int m = matrix.length, n = matrix[0].length;
dd = new DynamicDifference2D(m, n);
// 执行所有更新操作
for (int[] op : operations) {
int x1 = op[0], y1 = op[1];
int x2 = op[2], y2 = op[3];
int val = op[4];
dd.rangeAdd(x1, y1, x2, y2, val);
}
// 查询每个位置的值
int[][] result = new int[m][n];
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
result[i][j] = dd.pointQuery(i, j);
}
}
return result;
}
}
class Solution:
def getModifiedMatrix(self, matrix: List[List[int]], operations: List[List[int]]) -> List[List[int]]:
m, n = len(matrix), len(matrix[0])
dd = DynamicDifference2D(m, n)
# 执行所有更新操作
for x1, y1, x2, y2, val in operations:
dd.range_add(x1, y1, x2, y2, val)
# 查询每个位置的值
result = [[0] * n for _ in range(m)]
for i in range(m):
for j in range(n):
result[i][j] = dd.point_query(i, j)
return result
时间复杂度
- 初始化：
- 子矩阵修改：
- 单点查询：
- 空间复杂度：
动态差分 vs 静态差分
优点：
- 支持动态操作
- 单点查询更快
- 无需还原整个矩阵
缺点：
- 实现较复杂
- 常数较大
- 内存占用略多
注意事项
- 树状数组下标从1开始
- 子矩阵修改的边界处理
- 注意差分数组的范围
- 处理负数和溢出
练习建议
- 实现基本的二维动态差分
- 解决动态矩阵问题
- 比较静态和动态实现
- 尝试其他数据结构实现
牛客代码笔记-牛栋 文章被收录于专栏
汗牛充栋，学海无涯。<br/> 内含算法知识点讲解，以及牛客题库精选例题。<br/> 学习算法，从牛栋开始。
投递美团等公司6个岗位