LeetCode 二维树状数组题解

LeetCode 二维树状数组题解

题目描述

实现一个二维树状数组，支持以下操作：

1. 更新：更新某个位置的值
2. 查询：返回某个子矩阵的元素和

解题思路

方法：二维树状数组

思路：

• 将一维树状数组扩展到二维。
• 每个节点存储一个一维树状数组。

复杂度分析：

• 时间复杂度：O(log n * log m)。
• 空间复杂度：O(n * m)。

代码实现

class FenwickTree2D: def __init__(self, m, n): self.m = m self.n = n self.tree = [[0] * (n + 1) for _ in range(m + 1)] def update(self, x, y, delta): i = x while i <= self.m: j = y while j <= self.n: self.tree[i][j] += delta j += j & (-j) i += i & (-i) def query(self, x, y): result = 0 i = x while i > 0: j = y while j > 0: result += self.tree[i][j] j -= j & (-j) i -= i & (-i) return result def range_query(self, x1, y1, x2, y2): return self.query(x2, y2) - self.query(x1 - 1, y2) - self.query(x2, y1 - 1) + self.query(x1 - 1, y1 - 1) # 测试 def test_fenwick_tree_2d(): ft = FenwickTree2D(3, 3) ft.update(1, 1, 1) ft.update(2, 2, 2) print(ft.range_query(1, 1, 2, 2)) # 输出：3 if __name__ == "__main__": test_fenwick_tree_2d()

总结

二维树状数组是一维树状数组的扩展，可以高效地处理二维区域的查询和更新操作。