Hiểu bài toán

Bài toán yêu cầu xử lý m truy vấn trên một mảng gồm n số nguyên. Với mỗi truy vấn cho trước hai chỉ số x và y, ta cần tính tổng các phần tử trong mảng từ chỉ số x đến y (bao gồm cả x và y). Dữ liệu đầu vào có thể lên tới 10^5 phần tử và 10^5 truy vấn, nghĩa là nếu tính tổng lại từ đầu cho mỗi truy vấn, chương trình sẽ chạy rất chậm.

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

Cách Brute Force (Tính tổng trực tiếp)

#include <bits/stdc++.h>
using namespace std;
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n, m;
    cin >> n >> m;
    vector<long long> a(n + 1);
    for (int i = 1; i <= n; i++) cin >> a[i];
    while (m--) {
        int x, y;
        cin >> x >> y;
        long long sum = 0;
        for (int i = x; i <= y; i++) sum += a[i];
        cout << sum << "\n";
    }
    return 0;
}

• Time Complexity: O(n * m) trong trường hợp xấu nhất (ví dụ m=n=10^5, mỗi truy vấn bao gồm toàn bộ mảng)
• Space Complexity: O(n)

Với mỗi truy vấn, ta duyệt qua các phần tử từ x đến y và cộng dồn vào biến tổng. Cách này đơn giản để hiểu nhưng hiệu năng rất kém, không thể chấp nhận được với giới hạn dữ liệu lớn (10^5).

Cách Prefix Sum (Mảng cộng dồn)

#include <bits/stdc++.h>
using namespace std;
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n, m;
    cin >> n >> m;
    vector<long long> a(n + 1);
    for (int i = 1; i <= n; i++) cin >> a[i];
    vector<long long> pref(n + 1, 0);
    for (int i = 1; i <= n; i++) pref[i] = pref[i - 1] + a[i];
    while (m--) {
        int x, y;
        cin >> x >> y;
        cout << pref[y] - pref[x - 1] << "\n";
    }
    return 0;
}

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

Ta xây dựng một mảng cộng dồn (prefix sum) pref trong đó pref[i] là tổng các phần tử từ chỉ số 1 đến i. Sau đó, tổng từ x đến y được tính bằng công thức: pref[y] - pref[x-1]. Phương pháp này giúp giảm thời gian xử lý mỗi truy vấn xuống O(1) sau khi đã xây dựng mảng cộng dồn.

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

Bài học kinh nghiệm

• Sử dụng mảng cộng dồn (Prefix Sum) là kỹ thuật chuẩn để xử lý các truy vấn tổng trên đoạn liên tiếp trong mảng.
• Cần chuẩn hóa chỉ số mảng (ví dụ dùng từ 1 đến n) để tránh lỗi tràn số khi tính x-1 nếu x=0.

Lỗi thường gặp

• Lỗi tràn số (Integer Overflow): Tổng các phần tử có thể vượt quá giới hạn của kiểu int 32-bit (vì |a_i| <= 10^9 và n <= 10^5), do đó cần dùng kiểu dữ liệu lớn hơn như long long (64-bit).
• Lỗi chỉ số mảng: Khi truy vấn đoạn từ x đến y, nếu mảng bắt đầu từ 1, cần trừ đi pref[x-1]. Nếu không chú ý, có thể gây ra lỗi truy cập ngoài vùng nhớ hoặc sai kết quả.