二维动态前缀和（单修区查）

二维树状数组（2D Binary Indexed Tree）是树状数组在二维平面上的扩展，支持单点修改和子矩阵查询。
它能在 $\mathcal{O}(\log m \cdot \log n)$ 的时间复杂度内完成修改和查询操作。

基本概念

二维树状数组的核心思想是：

在两个维度上分别应用树状数组的思想
每个节点维护一个子矩阵的和
通过二进制特性快速定位和更新
支持动态修改的同时保持较快的查询速度

实现方式

二维树状数组的关键操作：

lowbit：获取二进制中最低位的1
update：单点修改
query：查询前缀和
sumRegion：子矩阵查询

基本实现

c++
java
python

class BIT2D {
private:
    vector<vector<int>> tree;
    int m, n;
    
    int lowbit(int x) {
        return x & (-x);
    }

public:
    BIT2D(int rows, int cols) : m(rows), n(cols) {
        tree.resize(m + 1, vector<int>(n + 1));
    }
    
    void update(int row, int col, int delta) {
        for (int i = row + 1; i <= m; i += lowbit(i)) {
            for (int j = col + 1; j <= n; j += lowbit(j)) {
                tree[i][j] += delta;
            }
        }
    }
    
    int query(int row, int col) {
        int sum = 0;
        for (int i = row + 1; i > 0; i -= lowbit(i)) {
            for (int j = col + 1; j > 0; j -= lowbit(j)) {
                sum += tree[i][j];
            }
        }
        return sum;
    }
    
    int sumRegion(int row1, int col1, int row2, int col2) {
        return query(row2, col2) - query(row2, col1 - 1) 
               - query(row1 - 1, col2) + query(row1 - 1, col1 - 1);
    }
};

class BIT2D {
    private int[][] tree;
    private int m, n;
    
    public BIT2D(int rows, int cols) {
        m = rows;
        n = cols;
        tree = new int[m + 1][n + 1];
    }
    
    private int lowbit(int x) {
        return x & (-x);
    }
    
    public void update(int row, int col, int delta) {
        for (int i = row + 1; i <= m; i += lowbit(i)) {
            for (int j = col + 1; j <= n; j += lowbit(j)) {
                tree[i][j] += delta;
            }
        }
    }
    
    public int query(int row, int col) {
        int sum = 0;
        for (int i = row + 1; i > 0; i -= lowbit(i)) {
            for (int j = col + 1; j > 0; j -= lowbit(j)) {
                sum += tree[i][j];
            }
        }
        return sum;
    }
    
    public int sumRegion(int row1, int col1, int row2, int col2) {
        return query(row2, col2) - query(row2, col1 - 1)
               - query(row1 - 1, col2) + query(row1 - 1, col1 - 1);
    }
}

class BIT2D:
    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, row, col, delta):
        i = row + 1
        while i <= self.m:
            j = col + 1
            while j <= self.n:
                self.tree[i][j] += delta
                j += self.lowbit(j)
            i += self.lowbit(i)
    
    def query(self, row, col):
        total = 0
        i = row + 1
        while i > 0:
            j = col + 1
            while j > 0:
                total += self.tree[i][j]
                j -= self.lowbit(j)
            i -= self.lowbit(i)
        return total
    
    def sum_region(self, row1, col1, row2, col2):
        return (self.query(row2, col2) - self.query(row2, col1 - 1)
                - self.query(row1 - 1, col2) + self.query(row1 - 1, col1 - 1))

应用场景

二维树状数组在很多问题中都有应用：

动态子矩阵和查询
图像处理和更新
二维平面点数统计
动态网格统计
游戏地图更新

示例：矩阵区域和

cpp
java
python

class NumMatrix {
private:
    BIT2D* bit;
    vector<vector<int>> matrix;
    
public:
    NumMatrix(vector<vector<int>>& matrix) {
        if (matrix.empty() || matrix[0].empty()) return;
        this->matrix = matrix;
        int m = matrix.size(), n = matrix[0].size();
        bit = new BIT2D(m, n);
        
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                bit->update(i, j, matrix[i][j]);
            }
        }
    }
    
    void update(int row, int col, int val) {
        int delta = val - matrix[row][col];
        matrix[row][col] = val;
        bit->update(row, col, delta);
    }
    
    int sumRegion(int row1, int col1, int row2, int col2) {
        return bit->sumRegion(row1, col1, row2, col2);
    }
};

class NumMatrix {
    private BIT2D bit;
    private int[][] matrix;
    
    public NumMatrix(int[][] matrix) {
        if (matrix == null || matrix.length == 0 || matrix[0].length == 0) return;
        this.matrix = new int[matrix.length][matrix[0].length];
        int m = matrix.length, n = matrix[0].length;
        bit = new BIT2D(m, n);
        
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                this.matrix[i][j] = matrix[i][j];
                bit.update(i, j, matrix[i][j]);
            }
        }
    }
    
    public void update(int row, int col, int val) {
        int delta = val - matrix[row][col];
        matrix[row][col] = val;
        bit.update(row, col, delta);
    }
    
    public int sumRegion(int row1, int col1, int row2, int col2) {
        return bit.sumRegion(row1, col1, row2, col2);
    }
}

class NumMatrix:
    def __init__(self, matrix: List[List[int]]):
        if not matrix or not matrix[0]:
            return
        self.matrix = [[0] * len(matrix[0]) for _ in range(len(matrix))]
        m, n = len(matrix), len(matrix[0])
        self.bit = BIT2D(m, n)
        
        for i in range(m):
            for j in range(n):
                self.matrix[i][j] = matrix[i][j]
                self.bit.update(i, j, matrix[i][j])
    
    def update(self, row: int, col: int, val: int) -> None:
        delta = val - self.matrix[row][col]
        self.matrix[row][col] = val
        self.bit.update(row, col, delta)
    
    def sumRegion(self, row1: int, col1: int, row2: int, col2: int) -> int:
        return self.bit.sum_region(row1, col1, row2, col2)