二维树状数组：让矩阵求和又快又准

想象一下，你正在管理一个班级的座位表，每个座位都有一位同学。老师在每节课后公布大家的额外加分（比如课堂表现分），你需要快速更新某个同学的总分，并且随时能算出任意一个矩形区域（比如第2行第3列到第5行第6列）内所有同学的总分。如果班上有100行100列，每次查询都逐个格子加一遍，计算量是10000次，而更新一个同学的分倒是很快（直接改一个格子）。但如果查询几百次，电脑就慢得像蜗牛一样了。

有没有像一维树状数组那样，能同时快速完成“单点修改”和“区间求和”的二维版本呢？当然有！二维树状数组就是在一维树状数组上再嵌套一层，每个节点管理一个矩形区域的和。它能在 O(log n × log m) 的时间里完成单点修改和子矩阵求和，而暴力修改是 O(1)，但查询是 O(n×m) —— 对于大矩阵，后者非常慢。

一、核心原理：二维前缀和与 lowbit 的嵌套

1.1 从一维到二维的飞跃

在一维树状数组中，tree[i] 管理的是原数组从 i - lowbit(i) + 1 到 i 这一段连续区间的和。这里的 lowbit(x) 是 x 的二进制中最低位的1所对应的值（例如 lowbit(6)=2，因为6的二进制是110，最低位1对应2）。

二维树状数组把同样的想法扩展到两个维度：tree[x][y] 管理的是原矩阵中行从 x - lowbit(x) + 1 到 x，列从 y - lowbit(y) + 1 到 y 这一块矩形区域的和。简单说，每个节点“管”一个矩形，矩形的右下角就是节点坐标 (x, y)，矩形的高是 lowbit(x)，宽是 lowbit(y)。

举个例子：假设矩阵有8行8列。

tree[4][6] 管理的是行区间 [1,4]（因为 lowbit(4)=4，起点=4-4+1=1），列区间 [5,6]（因为 lowbit(6)=2，起点=6-2+1=5），所以它管理的是行1~~4、列5~~6的 4×2 矩形。
tree[2][3] 管理的是行 [1,2]、列 [3,3] 的 2×1 矩形（相当于两行的一列）。
tree[1][1] 只管理点 (1,1) 自己。

1.2 更新操作：向下向右扩散

当你修改矩阵中某个点 (x, y) 的值（比如增加 delta），你要告诉所有“包含这个点”的 tree 节点。根据树状数组的规则，这些节点的行索引 i 从 x 开始，每次加上自己的 lowbit(i)，直到超过行数；列索引 j 也从 y 开始，每次加上自己的 lowbit(j)，直到超过列数。两层循环，就能更新所有必要的矩形。

为什么这样做是正确的？因为每个节点的管辖范围是连续的，而 i += lowbit(i) 恰好定位到所有覆盖了行 x 的更大矩形。列同理。这种“双重跳跃”正好对应一维树状数组的更新方式。

1.3 查询操作：前缀和 + 容斥原理

要得到左上角 (1,1) 到右下角 (x,y) 的矩形和（称为二维前缀和 sum(x, y)），我们反向走：从 (x, y) 开始，每次减去 lowbit，累加所有经过的 tree[i][j]。这和一维的 sum 操作类似，只是把一维的减 lowbit 换成了两层循环。

有了 sum(x, y)，任意子矩阵 (x1, y1) 到 (x2, y2) 的和就能用容斥原理求出：

子矩阵和 = sum(x2, y2) - sum(x1-1, y2) - sum(x2, y1-1) + sum(x1-1, y1-1)

这个公式和二维前缀和的公式完全一样，只不过这里的 sum 是通过树状数组快速得到的。

二、生活中的例子：班级成绩管理

假设有5行5列共25个座位，每个同学有一张答题卡，上面是平时的积分。我们需要：

随时给某个同学加分（比如回答正确加5分）；
快速查询某一块区域（比如第2排到第4排、第3列到第5列）的总积分。

用二维树状数组，每个修改和查询都只需要大约 log(5)*log(5) ≈ 4 步（因为5的二进制是101，lowbit值有1,2,4），而暴力查询需要数几十步。当矩阵变成1000×1000时，暴力查询需要100万步，而树状数组大约只需 log1000×log1000≈100 步，速度快了1万倍。

三、代码实现（含详细注释）

下面给出 C++ 和 Python 两个版本的完整实现。注意：矩阵的行和列编号都从 1 开始，这样写循环更方便。

C++ 实现

#include <iostream>
#include <vector>
using namespace std;

class Fenwick2D {
private:
    int n, m;                           // 行数、列数
    vector<vector<long long>> tree;     // 二维树状数组，下标从1开始

    int lowbit(int x) { return x & -x; } // 返回x的二进制最低位1对应的值

public:
    // 构造函数：初始化 n 行 m 列的矩阵，所有值0
    Fenwick2D(int n, int m) : n(n), m(m), tree(n + 1, vector<long long>(m + 1, 0)) {}

    // 单点修改：在 (x,y) 处增加 delta
    void add(int x, int y, long long delta) {
        for (int i = x; i <= n; i += lowbit(i)) {       // 外层循环：行跳跃
            for (int j = y; j <= m; j += lowbit(j)) {   // 内层循环：列跳跃
                tree[i][j] += delta;                    // 更新管辖这个点的矩形块
            }
        }
    }

    // 查询前缀和：从 (1,1) 到 (x,y) 的矩形和
    long long sum(int x, int y) {
        long long res = 0;
        for (int i = x; i > 0; i -= lowbit(i)) {        // 外层循环：行倒退
            for (int j = y; j > 0; j -= lowbit(j)) {    // 内层循环：列倒退
                res += tree[i][j];                      // 累加所有被包含的矩形块
            }
        }
        return res;
    }

    // 查询子矩阵和：左上角 (x1,y1) 到右下角 (x2,y2)
    long long rangeSum(int x1, int y1, int x2, int y2) {
        return sum(x2, y2) - sum(x1 - 1, y2) - sum(x2, y1 - 1) + sum(x1 - 1, y1 - 1);
    }
};

int main() {
    Fenwick2D ft(5, 5); // 创建一个5行5列的矩阵，所有格子初始为0

    // 假设有以下几个同学的加分情况
    ft.add(1, 1, 5);   // 第1行第1列的同学加5分
    ft.add(2, 3, 10);  // 第2行第3列加10分
    ft.add(4, 2, 7);   // 第4行第2列加7分
    ft.add(3, 4, 3);   // 第3行第4列加3分

    // 查询整个矩阵的总分
    cout << "整个矩阵的和: " << ft.rangeSum(1,1,5,5) << endl; // 5+10+7+3 = 25

    // 查询从第2行第2列到第4行第4列的矩形区域
    cout << "子矩阵[2,2]到[4,4]的和: " << ft.rangeSum(2,2,4,4) << endl; // 包含(2,3)=10, (3,4)=3, (4,2)=7 → 20

    // 查询单个点 (2,3) 的值
    cout << "单个点(2,3)的值: " << ft.rangeSum(2,3,2,3) << endl; // 10

    // 给第2行第3列的同学再追加5分
    ft.add(2, 3, 5);
    cout << "修改后子矩阵[2,2]到[4,4]的和: " << ft.rangeSum(2,2,4,4) << endl; // 10+5+3+7 = 25

    return 0;
}

Python 实现

class Fenwick2D:
    def __init__(self, n, m):
        self.n = n  # 行数
        self.m = m  # 列数
        # 创建 (n+1) x (m+1) 的列表，初始全0，下标从1开始
        self.tree = [[0] * (m + 1) for _ in range(n + 1)]

    def lowbit(self, x):
        """返回 x 的二进制最低位1对应的值"""
        return x & -x

    def add(self, x, y, delta):
        """单点修改：在 (x,y) 增加 delta"""
        i = x
        while i <= self.n:
            j = y
            while j <= self.m:
                self.tree[i][j] += delta
                j += self.lowbit(j)
            i += self.lowbit(i)

    def sum(self, x, y):
        """前缀和：从 (1,1) 到 (x,y) 的矩形和"""
        res = 0
        i = x
        while i > 0:
            j = y
            while j > 0:
                res += self.tree[i][j]
                j -= self.lowbit(j)
            i -= self.lowbit(i)
        return res

    def range_sum(self, x1, y1, x2, y2):
        """子矩阵和：左上角 (x1,y1) 到右下角 (x2,y2)"""
        return (self.sum(x2, y2) - self.sum(x1 - 1, y2) -
                self.sum(x2, y1 - 1) + self.sum(x1 - 1, y1 - 1))

if __name__ == "__main__":
    ft = Fenwick2D(5, 5)  # 5行5列，初始全0

    ft.add(1, 1, 5)   # 加5分
    ft.add(2, 3, 10)  # 加10分
    ft.add(4, 2, 7)   # 加7分
    ft.add(3, 4, 3)   # 加3分

    print("整个矩阵的和:", ft.range_sum(1,1,5,5))      # 25
    print("子矩阵[2,2]到[4,4]的和:", ft.range_sum(2,2,4,4)) # 20
    print("单个点(2,3)的值:", ft.range_sum(2,3,2,3)) # 10

    ft.add(2, 3, 5)   # 再追加5分
    print("修改后子矩阵[2,2]到[4,4]的和:", ft.range_sum(2,2,4,4)) # 25

四、常见错误与调试技巧

初学者在使用二维树状数组时容易犯以下错误：

坐标从0开始：树状数组的公式 i += lowbit(i) 要求下标从1开始，如果矩阵下标从0开始，更新和查询时都要先加1，否则循环会陷入死循环或越界。
忘记初始化大小：创建时一定要留出 (n+1) × (m+1) 的空间，确保下标1~~n、1~~m可用。
lowbit写错：x & -x 在C++中要确保 x 是整数，Python也一样。如果写成 x & (x-1) 会得到不同的结果。
查询子矩阵时边界处理不当：x1-1 或 y1-1 可能为0，但我们的 sum(0, any) 应该返回0，因为循环条件 i>0 会直接跳过。但要注意，如果 x1 是1，那么 x1-1=0，调用 sum(0, y2) 是正确的（返回0）。如果矩阵下标从0开始，则要小心。
数据类型溢出：如果矩阵中数值很大，累加可能超出 int 范围，建议使用 long long 或 int64。
二维数组的遍历顺序：外层循环是行，内层循环是列，不要搞反。虽然对称情况下结果一样，但逻辑上对应 lowbit 顺序。

调试小技巧

先用小矩阵（比如3×3）手动模拟，把每一步的 tree 值写出来，验证更新和查询是否正确。
使用 rangeSum(x, y, x, y) 获取单个点的值，确认与修改的值一致。
确保 sum(n, m) 等于所有格子的总和（可以用暴力求和验证）。

五、完整示例：游戏积分统计

假设你在设计一个 10×10 的游戏地图，每个格子可以放一个道具，玩家踩到道具会获得积分。现在需要支持：

在格子 (i, j) 放置或移除道具（即增加或减少积分）；
查询某个矩形区域（比如一块宝箱区域）内的总积分。

下面的代码演示了完整的操作流程，并输出结果。

# 游戏积分统计示例
ft = Fenwick2D(10, 10)

# 放置道具
ft.add(3, 4, 5)   # (3,4)位置有5分
ft.add(5, 7, 10)  # (5,7)位置有10分
ft.add(8, 2, 3)   # (8,2)位置有3分

# 查询区域 [2,3] 到 [6,8] 的总积分
area = ft.range_sum(2, 3, 6, 8)
print(f"区域[2,3]到[6,8]的总积分: {area}")  # 只包含(3,4)=5 和 (5,7)=10 → 15

# 移除 (3,4) 处的道具（即加 -5）
ft.add(3, 4, -5)
area2 = ft.range_sum(2, 3, 6, 8)
print(f"移除后区域积分: {area2}")  # 只剩下 (5,7)=10 → 10

输出结果：

区域[2,3]到[6,8]的总积分: 15
移除后区域积分: 10

六、总结与延伸

要点回顾

二维树状数组把一维的 lowbit 规则延展到两个维度，每个节点 tree[x][y] 管理一个矩形区域，行范围为 [x - lowbit(x) + 1, x]，列范围为 [y - lowbit(y) + 1, y]。
单点修改需要双重循环，每次向上跳转 lowbit 步，更新所有覆盖该点的矩形块，时间复杂度 O(log n × log m)。
子矩阵查询先通过二维前缀和求出任意 (1,1) 到 (x,y) 的和，再用容斥原理求任意矩形，复杂度同样 O(log n × log m)。
空间复杂度 O(n×m)，适合矩阵大小在几千以内的场景。对于超大矩阵（例如 10^5 级别），可能需要用稀疏化方法或线段树。

二维树状数组简介