Hiểu bài toán

Bài toán yêu cầu tính tổng các phần tử trong mảng từ chỉ số a đến chỉ số b cho nhiều truy vấn khác nhau. Input bao gồm số lượng phần tử của mảng, các phần tử của mảng, số lượng truy vấn, và các cặp chỉ số a, b của mỗi truy vấn. Với mỗi truy vấn, cần in ra tổng các phần tử từ chỉ số a đến chỉ số b (1-based indexing). Ví dụ: với mảng [100, 100, 200, 300, 500, -1, 600] và truy vấn (1, 2), kết quả là 100 + 100 = 200.

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

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

#include <iostream>
#include <vector>
using namespace std;

int main() {
    int n;
    cin >> n;
    vector<long long> a(n + 1);
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
    }
    int k;
    cin >> k;
    while (k--) {
        int l, r;
        cin >> l >> r;
        long long sum = 0;
        for (int i = l; i <= r; i++) {
            sum += a[i];
        }
        cout << sum << '\n';
    }
    return 0;
}

• Time Complexity: O(k * n) - Trong trường hợp xấu nhất, mỗi truy vấn duyệt qua toàn bộ mảng.
• Space Complexity: O(n) - Để lưu mảng a.

Cách tiếp cận này xử lý mỗi truy vấn bằng cách duyệt qua các phần tử từ chỉ số a đến b và cộng dồn lại. Đơn giản để hiểu nhưng hiệu quả kém khi số lượng truy vấn lớn.

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

#include <iostream>
#include <vector>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n;
    cin >> n;
    vector<long long> a(n + 1);
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
    }

    vector<long long> pre(n + 1, 0);
    for (int i = 1; i <= n; i++) {
        pre[i] = pre[i - 1] + a[i];
    }

    int k;
    cin >> k;
    while (k--) {
        int l, r;
        cin >> l >> r;
        cout << pre[r] - pre[l - 1] << '\n';
    }

    return 0;
}

• Time Complexity: O(n + k) - O(n) để xây dựng mảng cộng dồn, O(1) cho mỗi truy vấn.
• Space Complexity: O(n) - Để lưu mảng cộng dồn.

Sử dụng kỹ thuật Prefix Sum. Mảng pre được xây dựng sao cho pre[i] là tổng các phần tử từ a[1] đến a[i]. Tổng từ a đến b được tính bằng pre[b] - pre[a-1]. Đây là giải pháp tối ưu cho bài toán này.

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

Bài học kinh nghiệm

• Kỹ thuật Prefix Sum cho phép trả lời các truy vấn tổng đoạn trong O(1) sau O(n) tiền xử lý.
• Sử dụng kiểu dữ liệu long long để tránh tràn số khi tính tổng các phần tử lớn.

Lỗi thường gặp

• Quên trừ đi pre[a-1] hoặc sai lệch chỉ số mảng (1-based vs 0-based).
• Sử dụng int gây tràn số khi tổng các phần tử vượt quá giới hạn.