Truy vấn tổng vùng 2D - Có thể thay đổi trong C++

Cho ma trận 2D, cần tính tổng các phần tử trong hình chữ nhật xác định bởi góc trên trái và góc dưới phải. Hỗ trợ cả cập nhật giá trị phần tử.

Ví dụ: Ma trận 5x5, vùng xanh từ (2,1) đến (4,3) có tổng = 8. Sau update(3,2,2), tổng thành 10.

Phương pháp giải

Sử dụng Binary Indexed Tree 2D (Fenwick Tree 2D). Cây tree[][] lưu trữ tổng tiền tố. Cập nhật: thêm delta vào các nút liên quan. Truy vấn tổng tiền tố: cộng các nút trên đường đi. Tổng vùng = sum(row2,col2) + sum(row1-1,col1-1) - sum(row1-1,col2) - sum(row2,col1-1).

Ví dụ chương trình

#include <bits/stdc++.h>
using namespace std;

class NumMatrix {
public:
    int n, m;
    vector> tree;
    vector> value;
    
    NumMatrix(vector>& matrix) {
        n = matrix.size();
        m = n ? matrix[0].size() : 0;
        value = vector>(n, vector(m));
        tree = vector>(n + 1, vector(m + 1));
        for (int i = 0; i < n; i++)
            for (int j = 0; j < m; j++)
                update(i, j, matrix[i][j]);
    }
    
    void update(int row, int col, int val) {
        if (n == 0 || m == 0) return;
        int delta = val - value[row][col];
        value[row][col] = val;
        for (int i = row + 1; i <= n; i += i & (-i))
            for (int j = col + 1; j <= m; j += j & (-j))
                tree[i][j] += delta;
    }
    
    int sum(int row, int col) {
        int ret = 0;
        for (int i = row; i > 0; i -= i & (-i))
            for (int j = col; j > 0; j -= j & (-j))
                ret += tree[i][j];
        return ret;
    }
    
    int sumRegion(int row1, int col1, int row2, int col2) {
        if (m == 0 || n == 0) return 0;
        row2++; row1++; col1++; col2++;
        return sum(row2, col2) + sum(row1 - 1, col1 - 1) 
             - sum(row1 - 1, col2) - sum(row2, col1 - 1);
    }
};

int main() {
    vector> v = {
        {3, 0, 1, 4, 2},
        {5, 6, 3, 2, 1},
        {1, 2, 0, 1, 5},
        {4, 1, 0, 1, 7},
        {1, 0, 3, 0, 5}
    };
    NumMatrix ob(v);
    cout << ob.sumRegion(2, 1, 4, 3) << endl;
    ob.update(3, 2, 2);
    cout << ob.sumRegion(2, 1, 4, 3) << endl;
    return 0;
}

Đầu vào

Ma trận 5x5, sumRegion(2,1,4,3), update(3,2,2), sumRegion(2,1,4,3)

Đầu ra

8 10