二维二叉索引树或 Fenwick 树

二维树状数组（2D BIT），也常被称为 Fenwick 树，是一种复杂的二维数据结构，用于通过维护累积和或频率来快速更新和查询二维数组（矩阵）。

2D BIT 将一维 BIT（它有效地计算线性数组中的前缀和）的思想扩展到二维设置。它支持对二维矩阵进行快速更新和范围查询。这在图像处理、动态规划以及需要以网格状格式维护累积数据的各种数学技术等应用中非常有用。

2D BIT 结构使用两个索引：行和列。其基本概念是可视化不同矩阵中值的累积和（或频率）。通过利用位运算处理索引，可以高效地遍历 BIT 以计算累积和并执行更新。

以下是 2D BIT 的工作原理说明

• 初始化

定义二维矩阵的维度： 您必须指定要创建 2D BIT 的二维矩阵的维度。假设矩阵的维度为 max_x（最大行数）和 max_y（最大列数）。

创建 2D BIT 数组： 初始化一个名为 BIT 的二维数组，其维度为 (max_x + 1) (max_y + 1)。所有值都设置为 0。为了适应 1-based 索引（通常与 BIT 一起使用），维度增加了 1。

定义 BIT 更新和查询函数： 2D BIT 和查询累积和将分别使用 getSum 和 updateBIT 方法进行更新。与 1D BIT 不同，这些函数现在同时考虑行和列索引。

初始化 2D BIT： 通过更新原始矩阵的每个元素从头开始创建 2D BIT。如果您已经有一个名为 matrix 的 2D 矩阵，您可以使用 updateBIT 方法遍历它并更新 2D BIT 中相关的单元格。

• 更新操作

更新函数： 在 2D BIT 中，更新操作包括向 BIT 数组中的特定单元格添加一个值，并通过数据结构传播此更新的影响以维护累积和。

位操作：为了有效地遍历 2D BIT，使用位操作，特别是位与 (&) 和补码 (-)。

更新过程： 假设您希望将值 val 添加到原始矩阵中点 (x, y) 处的值。您可以按如下方式执行更新

外层和内层 while 循环分别遍历行和列。

将更新值 val 添加到 BIT 数组中的每个单元格 (x, y)。

为了分别移动到同一行或下一行中的下一个相应单元格，使用表达式 y & -y 和 x & -x。

更新操作示例

假设您希望将 5 添加到原始矩阵中位置 (2, 3) 处的值。将按如下方式调用 updateBIT 函数

updateBIT(2, 3, 5)

更新过程将通过相关单元格传播此更改，将 5 添加到 BIT 数组中的单元格 (2, 3)。

为了方便有效的范围和查询，此更新过程确保累积和准确地保存在 BIT 结构中。

这些更新过程允许 2D BIT 在准确反映原始矩阵更改的同时快速计算累积和。

• 查询操作

在 2D BIT 中，查询操作是计算原始矩阵中某个子矩阵内值的总和。为此，需要减去排除区域的累积和，然后将双重排除区域重新添加回来。

位操作： 为了有效地遍历 2D BIT，与更新操作类似，使用位操作（位与 & 和补码 -）。

查询过程： 假设您希望找到原始矩阵中由左下角 (x1, y1) 和右上角 (x2, y2) 定义的子矩阵中值的总和。

外层和内层 while 循环分别遍历行和列。

将子矩阵中每个单元格 (x2, y2) 的值添加到总和中。

要分别移动到同一行或上一行中上一个相关单元格，请使用表达式 y2 & -y2 和 x2 & -x2。

减法和加法： 您使用下面显示的方法来确定由 (x1, y1) 和 (x2, y2) 定义的子矩阵内的总和

sum_submatrix = queryBIT(x2, y2) - queryBIT(x2, y1 - 1) - queryBIT(x1 - 1, y2) + queryBIT(x1 - 1, y1 - 1)

queryBIT(x2, y2) 给出整个子矩阵的总和。

queryBIT(x2, y1 - 1) 减去排除的右上角的总和。

queryBIT(x1 - 1, y2) 减去排除的左下角的总和。

queryBIT(x1 - 1, y1 - 1) 重新加上双重排除的左上角的总和。

算法

我们考虑下面的例子。假设我们需要计算高亮区域中所有数字的总和。

我们认为 O 是矩阵左下角的原点。2D BIT 然后利用这一点，通过

高亮区域下方的总和等于 Sum(OB) + Sum(OD) + Sum(OA) + Sum(OC)

我们的软件中使用 getSum(x, y) 函数，该函数计算从 (0, 0) 到 (x, y) 的矩阵总和。

因此，以下公式

高亮区域中的总和等于 Sum(OB) - Sum(OD) Sum(OA) 减去 Sum(OC)

上述公式的结果是：

查询 (x1, y1, x2, y2) 的公式是 getSum(x2, y2) = getSum(x2, y1-1) - getSum(x1-1, y2) + getSum(x1-1, y1-1)。

其中 C 的坐标是 x1, y1, y2，B 的坐标是 x2, y2, y。

updateBIT(x, y, val) 函数更新 (x, y) 到 (N, M) 区域内的所有元素，其中 N 是整个矩阵的最大 X 坐标。

M 是整个矩阵中的最高 Y 坐标。

其余过程与一维树状数组过程非常相似。

实施

在 Python 中

输出

Query (1, 1, 3, 2) = 30
Query (2, 3, 3, 3) = 8
Query (1, 1, 1, 1) = 1

查询 (1, 1, 3, 2) 将子矩阵 [(1, 1), (3, 2)] 的值相加，结果为 3 + 8 + 1 + 6 + 7 + 5 = 30。

查询 (2, 3, 3, 3) 将子矩阵 [(2, 3), (3, 3)] 的值相加，结果为 7 + 5 = 12。

查询 (1, 1, 1, 1) 确定子矩阵 [(1, 1), (1, 1)] 的值之和为 1。

应用程序使用 2D 树状数组 (2D BIT) 有效地计算这些结果。