动态矩阵区域和查询与更新

题目

动态矩阵区域和查询与更新

信息

• 类型：问答
• 难度：⭐⭐⭐

考点

二维前缀和,树状数组/线段树,差分思想,动态更新处理

快速回答

该问题要求设计支持动态更新和区域求和的数据结构，核心解决方案是：

• 使用二维树状数组或线段树实现高效更新和查询
• 初始化时间复杂度：O(mn logm logn)
• 更新操作时间复杂度：O(logm logn)
• 查询操作时间复杂度：O(logm logn)
• 关键技巧：
  • 树状数组的二维扩展
  • 差分思想处理增量
  • 坐标偏移处理边界

问题核心分析

题目要求设计数据结构支持：

1. 初始化 m×n 零矩阵
2. update(row, col, val)：更新元素值
3. sumRegion(row1, col1, row2, col2)：计算矩形区域和

在频繁更新和查询场景下，二维前缀和的静态特性无法满足要求，需要动态数据结构。

解决方案：二维树状数组

树状数组（Fenwick Tree）通过巧妙的位运算实现高效更新和前缀和查询：

class BinaryIndexedTree2D:
    def __init__(self, m, n):
        self.m = m
        self.n = n
        self.tree = [[0] * (n + 1) for _ in range(m + 1)]
        self.matrix = [[0] * n for _ in range(m)]

    def update(self, row, col, val):
        diff = val - self.matrix[row][col]
        self.matrix[row][col] = val
        i = row + 1
        while i <= self.m:
            j = col + 1
            while j <= self.n:
                self.tree[i][j] += diff
                j += j & -j  # 低位操作
            i += i & -i

    def query(self, row, col):
        res = 0
        i = row + 1
        while i > 0:
            j = col + 1
            while j > 0:
                res += self.tree[i][j]
                j -= j & -j
            i -= i & -i
        return res

    def sumRegion(self, row1, col1, row2, col2):
        return (self.query(row2, col2) 
                - self.query(row1 - 1, col2) 
                - self.query(row2, col1 - 1) 
                + self.query(row1 - 1, col1 - 1))

原理说明

• 树状数组结构：二维树状数组是嵌套的一维树状数组，每个节点管理子矩阵的和
• 更新操作：通过i += i & -i遍历所有父节点更新差值
• 查询操作：利用i -= i & -i累加前缀和
• 区域求和：应用二维前缀和容斥原理：
  sum(ABCD) = sum(OD) - sum(OB) - sum(OC) + sum(OA)

最佳实践

• 空间优化：使用一维数组模拟二维结构（行优先存储）
• 惰性初始化：对于稀疏矩阵动态创建节点
• 批量更新：差分数组+树状数组处理区间更新
• 替代方案：
  • 线段树：支持更复杂的区间操作，但代码复杂度更高
  • 分块处理：当矩阵极大时可按块分区管理

常见错误

• 边界处理：忘记坐标+1偏移导致索引越界
• 更新逻辑：直接赋值而非计算差值（diff = val - old_val）
• 区域求和：容斥原理符号错误（尤其左下角重复相减）
• 性能陷阱：使用暴力法（O(mn)更新或O(1)更新+O(mn)查询）

扩展知识

• 更高维度：三维树状数组（d>0; d -= d & -d嵌套）
• 动态开点：使用指针或字典避免全矩阵初始化
• 结合差分：
  1. 定义差分数组 D[i][j] = matrix[i][j] - matrix[i-1][j] - matrix[i][j-1] + matrix[i-1][j-1]
  2. 更新时只需修改差分数组四个角
  3. 通过二维前缀和恢复原矩阵
• 实际应用：图像处理（像素更新/区域统计）、物理仿真（粒子密度计算）、金融分析（实时区域数据聚合）