Hiểu bài toán

Bài toán yêu cầu tính t tổng các phần tử trong một hình chữ nhật con của bảng 2 chiều với kích thước m x n. Có t truy vấn, mỗi truy vấn cho tọa độ của hai góc đối diện (a, b) và (c, d) của hình chữ nhật, và cần in ra tổng các phần tử bên trong hình chữ nhật đó. Các số trong bảng có thể âm và có trị tuyệt đối lớn (đến ~10^9), do đó cần sử dụng kiểu dữ liệu 64-bit (long long).

Các cách tiếp cận

Cách Bổ sung tiền tố 2 chiều (2D Prefix Sum)

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

int main() {
    ios_base::sync_with_stdio(0); cin.tie(0);
    int m, n, t;
    while (cin >> m >> n >> t) {
        // Sử dụng mảng 2D hoặc vector
        // dp[i][j] lưu tổng các phần tử từ (1,1) đến (i,j)
        vector<vector<long long>> dp(m + 1, vector<long long>(n + 1, 0));

        for (int i = 1; i <= m; i++) {
            for (int j = 1; j <= n; j++) {
                long long val;
                cin >> val;
                // Công thức tính tổng tiền tố
                dp[i][j] = dp[i - 1][j] + dp[i][j - 1] - dp[i - 1][j - 1] + val;
            }
        }

        while (t--) {
            int a, b, c, d;
            cin >> a >> b >> c >> d;
            // Công thức tính tổng hình chữ nhật
            long long ans = dp[c][d] - dp[a - 1][d] - dp[c][b - 1] + dp[a - 1][b - 1];
            cout << ans << '\n';
        }
    }
    return 0;
}

• Time Complexity: O(m*n + t)
• Space Complexity: O(m*n)

Phương pháp này sử dụng kỹ thuật tiền tố (Prefix Sum) mở rộng lên 2 chiều. Chúng ta xây dựng một bảng phụ dp trong đó dp[i][j] là tổng các phần tử từ ô (1,1) đến ô (i,j). Quá trình xây dựng bảng này mất O(m*n). Sau đó, với mỗi truy vấn, ta có thể tính tổng của hình chữ nhật bất kỳ bằng công thức: Tổng(c,d) - Tổng(a-1,d) - Tổng(c,b-1) + Tổng(a-1,b-1). Mỗi truy vấn chỉ mất O(1) thời gian. Đây là cách tiếp cận tối ưu cho các bài toán tổng tiền tố.

Cách Brute Force (Duyệt trực tiếp)

// Pseudocode minh họa (không khuyến khích nộp)
void brute_force() {
    int m, n, t;
    cin >> m >> n >> t;
    long long a[m+1][n+1];
    // Đọc dữ liệu vào mảng a
    for(int i=1; i<=m; i++)
        for(int j=1; j<=n; j++) cin >> a[i][j];

    while(t--) {
        int r1, c1, r2, c2;
        cin >> r1 >> c1 >> r2 >> c2;
        long long sum = 0;
        // Duyệt qua từng ô trong hình chữ nhật
        for(int i = r1; i <= r2; i++) {
            for(int j = c1; j <= c2; j++) {
                sum += a[i][j];
            }
        }
        cout << sum << "\n";
    }
}

• Time Complexity: O(mnt) ~ O(200*200*40000) ~ 1.6*10^9 thao tác
• Space Complexity: O(m*n)

Đây là cách giải quyết trực quan nhất. Với mỗi truy vấn, ta duyệt qua tất cả các ô thuộc hình chữ nhật được chỉ định và cộng dồn giá trị. Tuy nhiên, với giới hạn của bài toán (m, n lên tới 200 và t lên tới 40000), độ phức tạp thời gian O(mnt) sẽ rất lớn và chắc chắn gây ra lỗi 'Time Limit Exceeded' (TLE). Phương pháp này chỉ hiệu quả khi m, n, t都非常 nhỏ.

Phân tích độ phức tạp

Bài học kinh nghiệm

• Kỹ thuật 2D Prefix Sum (Bổ sung tiền tố 2 chiều) cho phép trả lời mỗi truy vấn tổng hình chữ nhật con chỉ trong thời gian O(1) sau khi đã preprocess O(m*n).
• Luôn luôn sử dụng kiểu dữ liệu 64-bit (long long trong C++) cho các biến t tổng và mảng tiền tố khi giá trị đầu vào có thể lớn (lên tới 10^9) hoặc số lượng phần tử nhiều, tránh tràn số.

Lỗi thường gặp

• Lỗi tràn số (Integer Overflow): Nếu dùng int để lưu tổng, t tổng của toàn bộ bảng có thể vượt quá giới hạn của int (khoảng 2*10^9). Cần dùng long long.
• Truy cập sai chỉ số mảng: Khi tính tổng theo công thức tiền tố, cần chú ý xử lý trường hợp rìa (khi a=1 hoặc b=1). Việc khai báo mảng phụ có kích thước lớn hơn (ví dụ dp[m+1][n+1] và bắt đầu từ chỉ số 1) giúp tránh lỗi truy cập mảng âm và đơn giản hóa công thức.