Truy vấn tổng vùng 2D - Immutable trong C++

Cho ma trận 2D, cần xử lý nhiều truy vấn tính tổng các phần tử trong hình chữ nhật con xác định bởi góc trên-trái (row1, col1) và góc dưới-phải (row2, col2).

Ví dụ ma trận 5x5, truy vấn sumRegion(2,1,4,3) trả về 8.

Thuật toán giải quyết (Prefix Sum 2D)

1. Xây dựng ma trận tiền tố dp kích thước n x m:
   • dp[i][j] = tổng các phần tử từ (0,0) đến (i,j).
   • Tính hàng ngang trước: dp[i][j] = (j>0 ? dp[i][j-1] : 0) + matrix[i][j].
   • Sau đó cộng dọc: dp[i][j] += (i>0 ? dp[i-1][j] : 0).
2. Truy vấn sumRegion(r1, c1, r2, c2):
   • ret = dp[r2][c2].
   • sub1 = (r1>0) ? dp[r1-1][c2] : 0.
   • sub2 = (c1>0) ? dp[r2][c1-1] : 0.
   • add = (r1>0 && c1>0) ? dp[r1-1][c1-1] : 0.
   • Kết quả = ret - sub1 - sub2 + add.

Ví dụ minh họa (C++)

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

class NumMatrix {
    vector<vector<int>> dp;
public:
    NumMatrix(vector<vector<int>>& matrix) {
        int n = matrix.size();
        if (!n) return;
        int m = matrix[0].size();
        dp.assign(n, vector<int>(m));
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                dp[i][j] = (j ? dp[i][j-1] : 0) + matrix[i][j];
            }
        }
        for (int i = 1; i < n; i++) {
            for (int j = 0; j < m; j++) {
                dp[i][j] += dp[i-1][j];
            }
        }
    }
    int sumRegion(int r1, int c1, int r2, int c2) {
        int ret = dp[r2][c2];
        int sub1 = r1 ? dp[r1-1][c2] : 0;
        int sub2 = c1 ? dp[r2][c1-1] : 0;
        int add = (r1 && c1) ? dp[r1-1][c1-1] : 0;
        return ret - sub1 - sub2 + add;
    }
};

int main() {
    vector<vector<int>> mat = {{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(mat);
    cout << ob.sumRegion(2,1,4,3) << endl;
    cout << ob.sumRegion(1,1,2,2) << endl;
    cout << ob.sumRegion(1,2,2,4) << endl;
}

Đầu vào

[[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]] sumRegion(2,1,4,3) sumRegion(1,1,2,2) sumRegion(1,2,2,4)

Đầu ra

8 11 12