Bài 17.3: Kỹ thuật mảng cộng dồn trong C++

Chào mừng các bạn quay trở lại với chuỗi bài viết về C++ và giải thuật! Hôm nay, chúng ta sẽ cùng khám phá một kỹ thuật cực kỳ hữu ích và hiệu quả trong lập trình cạnh tranh cũng như giải quyết các bài toán thực tế: Kỹ thuật mảng cộng dồn, hay còn gọi là Prefix Sum.

Hãy tưởng tượng bạn được cho một danh sách dài các con số và nhận hàng loạt yêu cầu tính tổng của các đoạn con khác nhau trong danh sách đó. Ví dụ, tổng từ vị trí 5 đến 10, sau đó từ 20 đến 35, rồi lại từ 1 đến 5,... Nếu danh sách có hàng triệu phần tử và số lượng yêu cầu lên tới hàng nghìn, việc tính tổng từng đoạn một theo cách thông thường (duyệt qua từng phần tử trong đoạn) sẽ rất chậm và tốn kém tài nguyên.

Đó chính là lúc kỹ thuật mảng cộng dồn tỏa sáng! Nó giúp chúng ta trả lời các truy vấn tổng đoạn con một cách nhanh như chớp, chỉ trong thời gian hằng số O(1) sau một bước tiền xử lý ban đầu.

Mảng Cộng Dồn là gì?

Mảng cộng dồn (Prefix Sum Array) là một mảng mới được xây dựng từ mảng gốc. Mỗi phần tử tại chỉ số i của mảng cộng dồn sẽ lưu trữ tổng của tất cả các phần tử từ đầu mảng gốc (chỉ số 0 hoặc 1, tùy cách đánh chỉ số) cho đến chỉ số i đó.

Nếu mảng gốc của chúng ta là arr có kích thước N, mảng cộng dồn prefix_sum cũng có kích thước tương tự (hoặc N+1 nếu dùng 1-based index). Với 0-based index: prefix_sum[0] = arr[0] prefix_sum[1] = arr[0] + arr[1] prefix_sum[i] = arr[0] + arr[1] + ... + arr[i]

Một cách nhìn khác đệ quy hơn, và dễ xây dựng hơn: prefix_sum[i] = prefix_sum[i-1] + arr[i] (với i > 0)

Cách Xây Dựng Mảng Cộng Dồn

Việc xây dựng mảng cộng dồn chỉ cần một lần duyệt qua mảng gốc. Độ phức tạp thời gian để xây dựng là O(N), với N là kích thước mảng.

Đây là ví dụ minh họa cách xây dựng mảng cộng dồn trong C++ sử dụng vector:

#include <iostream>
#include <vector>
#include <numeric> // Cần thiết nếu bạn muốn sử dụng partial_sum, nhưng ta sẽ tự code để hiểu rõ hơn

int main() {
    // Mảng gốc (ví dụ)
    vector<int> arr = {10, 20, 30, 40, 50};
    int n = arr.size();

    // Khởi tạo mảng cộng dồn. Sử dụng long long để tránh tràn số nếu tổng lớn.
    vector<long long> prefix_sum(n);

    // Xây dựng mảng cộng dồn
    prefix_sum[0] = arr[0]; // Phần tử đầu tiên của mảng cộng dồn
    for (int i = 1; i < n; ++i) {
        prefix_sum[i] = prefix_sum[i-1] + arr[i];
    }

    // In mảng gốc và mảng cộng dồn để kiểm tra
    cout << "Original array: ";
    for (int x : arr) {
        cout << x << " ";
    }
    cout << endl;

    cout << "Prefix Sum array: ";
    for (long long sum : prefix_sum) {
        cout << sum << " ";
    }
    cout << endl;

    return 0;
}

Giải thích code:

Chúng ta khai báo một vector<int> là arr chứa dữ liệu gốc.
Khai báo vector<long long> là prefix_sum cùng kích thước để lưu trữ mảng cộng dồn. Sử dụng long long là một thực hành tốt để đảm bảo tổng không bị tràn số, đặc biệt khi các giá trị trong mảng gốc lớn hoặc mảng dài.
prefix_sum[0] được gán bằng arr[0] vì tổng từ đầu đến chỉ số 0 chính là giá trị tại chỉ số 0.
Vòng lặp từ i = 1 đến n-1 tính toán từng phần tử tiếp theo của prefix_sum bằng cách cộng giá trị của phần tử trước đó trong prefix_sum (prefix_sum[i-1]) với giá trị hiện tại trong mảng gốc (arr[i]).

Kết quả chạy chương trình trên sẽ cho thấy mảng cộng dồn: 10 30 60 100 150.

Sử Dụng Mảng Cộng Dồn Để Truy Vấn Tổng Đoạn

Đây là lúc sức mạnh của mảng cộng dồn được thể hiện. Với mảng prefix_sum đã được xây dựng, chúng ta có thể tính tổng của bất kỳ đoạn con [l, r] nào (bao gồm cả arr[l] và arr[r], sử dụng 0-based index) chỉ bằng một phép trừ đơn giản:

Tổng của đoạn [l, r] = prefix_sum[r] - prefix_sum[l-1]

Nhưng chờ đã! Điều gì xảy ra nếu l là 0? Khi đó l-1 là -1, không hợp lệ. Vì prefix_sum[r] là tổng từ arr[0] đến arr[r], nên nếu đoạn bắt đầu từ chỉ số 0 (l=0), tổng của đoạn [0, r] chính là prefix_sum[r].

Vậy công thức đầy đủ là:

Nếu l == 0: Tổng là prefix_sum[r]
Nếu l > 0: Tổng là prefix_sum[r] - prefix_sum[l-1]

Hãy xem ví dụ minh họa trong C++:

#include <iostream>
#include <vector>

int main() {
    // Mảng gốc và mảng cộng dồn (đã xây dựng từ ví dụ trước)
    vector<int> arr = {10, 20, 30, 40, 50}; // n = 5
    vector<long long> prefix_sum = {10, 30, 60, 100, 150};

    // Các truy vấn tổng đoạn (sử dụng 0-based index [l, r])
    int l1 = 1, r1 = 3; // Đoạn từ chỉ số 1 đến 3: arr[1], arr[2], arr[3] -> 20 + 30 + 40 = 90
    int l2 = 0, r2 = 4; // Đoạn từ chỉ số 0 đến 4: arr[0]..arr[4] -> 10 + 20 + 30 + 40 + 50 = 150
    int l3 = 2, r3 = 2; // Đoạn tại chỉ số 2: arr[2] -> 30

    // Tính tổng cho từng truy vấn
    long long sum1 = (l1 == 0) ? prefix_sum[r1] : prefix_sum[r1] - prefix_sum[l1 - 1];
    long long sum2 = (l2 == 0) ? prefix_sum[r2] : prefix_sum[r2] - prefix_sum[l2 - 1];
    long long sum3 = (l3 == 0) ? prefix_sum[r3] : prefix_sum[r3] - prefix_sum[l3 - 1];

    // In kết quả
    cout << "Sum of range [" << l1 << ", " << r1 << "]: " << sum1 << endl; // Expected: 90
    cout << "Sum of range [" << l2 << ", " << r2 << "]: " << sum2 << endl; // Expected: 150
    cout << "Sum of range [" << l3 << ", " << r3 << "]: " << sum3 << endl; // Expected: 30

    return 0;
}

Giải thích code:

Chúng ta sử dụng mảng prefix_sum đã tính toán ở bước trước.
Với mỗi cặp chỉ số [l, r] của truy vấn, chúng ta áp dụng công thức: nếu l == 0, tổng là prefix_sum[r]. Nếu l > 0, tổng là prefix_sum[r] - prefix_sum[l-1].
Ví dụ [1, 3]: Tổng = prefix_sum[3] - prefix_sum[1-1] = prefix_sum[3] - prefix_sum[0] = 100 - 10 = 90. Chính xác là 20 + 30 + 40.
Ví dụ [0, 4]: Tổng = prefix_sum[4] (vì l = 0) = 150. Chính xác là tổng của cả mảng.
Ví dụ [2, 2]: Tổng = prefix_sum[2] - prefix_sum[2-1] = prefix_sum[2] - prefix_sum[1] = 60 - 30 = 30. Chính xác là arr[2].

Như bạn thấy, mỗi truy vấn chỉ cần một hoặc hai phép truy cập mảng và một phép trừ. Đây chính là độ phức tạp O(1)!

Tại Sao Kỹ Thuật Này Hiệu Quả?

Thời gian xây dựng: O(N) - chỉ cần duyệt mảng gốc một lần.
Thời gian truy vấn: O(1) - mỗi truy vấn chỉ cần một phép trừ (và kiểm tra biên).
Bộ nhớ bổ sung: O(N) để lưu mảng cộng dồn.

So sánh với cách tiếp cận "ngây thơ" (naive) là duyệt qua từng phần tử trong đoạn [l, r] cho mỗi truy vấn:

Thời gian xây dựng: O(1) - không cần tiền xử lý.
Thời gian truy vấn: O(r-l+1), trong trường hợp xấu nhất có thể là O(N) nếu đoạn truy vấn là cả mảng.
Bộ nhớ bổ sung: O(1).

Nếu bạn chỉ có một vài truy vấn, cách "ngây thơ" có thể chấp nhận được. Tuy nhiên, nếu số lượng truy vấn Q là lớn (ví dụ, Q >> 1), thì tổng thời gian cho cách "ngây thơ" là O(N Q), trong khi sử dụng mảng cộng dồn chỉ là O(N + Q). Với N và Q lớn, O(N+Q) là một cải tiến đột phá so với O(NQ).

Ví dụ cuối cùng: Nhiều truy vấn trên mảng lớn hơn

Giả sử chúng ta có một mảng 1000 phần tử và cần trả lời 500 truy vấn tổng đoạn.

Cách Naive: Khoảng 500 * (trung bình 500 phép cộng) = 250,000 phép cộng.
Mảng cộng dồn: 1000 phép cộng (xây dựng) + 500 * 1 phép trừ (truy vấn) = 1500 phép tính.

Sự khác biệt là khổng lồ!

#include <iostream>
#include <vector>
#include <numeric> // For iota, useful for generating test data
#include <chrono>  // For timing

int main() {
    int n = 100000; // Kích thước mảng lớn
    vector<int> arr(n);
    // Khởi tạo mảng với các giá trị đơn giản (ví dụ: 1, 2, 3, ...)
    iota(arr.begin(), arr.end(), 1);

    // --- Xây dựng mảng cộng dồn ---
    auto start_build = chrono::high_resolution_clock::now();
    vector<long long> prefix_sum(n);
    prefix_sum[0] = arr[0];
    for (int i = 1; i < n; ++i) {
        prefix_sum[i] = prefix_sum[i-1] + arr[i];
    }
    auto end_build = chrono::high_resolution_clock::now();
    chrono::duration<double> build_duration = end_build - start_build;
    cout << "Build time: " << build_duration.count() << " seconds" << endl;

    // --- Thực hiện các truy vấn ---
    int num_queries = 50000; // Số lượng truy vấn lớn
    long long total_sum_of_queries = 0; // Biến để tránh compiler tối ưu hóa bỏ qua phép tính

    auto start_query = chrono::high_resolution_clock::now();
    for (int i = 0; i < num_queries; ++i) {
        // Chọn ngẫu nhiên l, r (hoặc theo logic bài toán)
        // Ở đây ví dụ truy vấn các đoạn khác nhau
        int l = i % (n / 2);
        int r = l + (n / 2) - 1;
        if (r >= n) r = n - 1; // Đảm bảo r hợp lệ

        long long current_sum = (l == 0) ? prefix_sum[r] : prefix_sum[r] - prefix_sum[l - 1];
        total_sum_of_queries += current_sum; // Cộng dồn để đảm bảo tính toán được thực hiện
    }
    auto end_query = chrono::high_resolution_clock::now();
    chrono::duration<double> query_duration = end_query - start_query;
    cout << "Query time (" << num_queries << " queries): " << query_duration.count() << " seconds" << endl;
    // In tổng các kết quả để biến total_sum_of_queries không bị tối ưu hóa
    cout << "Total sum of all query results (dummy): " << total_sum_of_queries << endl;


    // So sánh (Nếu code naive, thời gian query sẽ lâu hơn đáng kể)
    // Ví dụ code naive cho 1 truy vấn (để bạn hình dung thời gian nếu làm 50000 lần)
    int naive_l = 10000, naive_r = 90000;
    auto start_naive = chrono::high_resolution_clock::now();
    long long naive_sum = 0;
    for (int i = naive_l; i <= naive_r; ++i) {
        naive_sum += arr[i];
    }
     auto end_naive = chrono::high_resolution_clock::now();
    chrono::duration<double> naive_duration = end_naive - start_naive;
    cout << "Naive sum for one range [" << naive_l << ", " << naive_r << "]: " << naive_sum << endl;
    cout << "Naive time for ONE query: " << naive_duration.count() << " seconds" << endl;
    // Nếu làm 50000 truy vấn như thế này, thời gian sẽ là naive_duration * 50000 (khoảng)

    return 0;
}

Giải thích Code:

Chúng ta tạo một mảng arr rất lớn (100000 phần tử) và điền các giá trị đơn giản bằng iota.
Đo thời gian xây dựng mảng cộng dồn. Bạn sẽ thấy nó rất nhanh (O(N)).
Thực hiện 50000 truy vấn tổng đoạn khác nhau. Mỗi truy vấn được tính chỉ trong O(1).
Đo thời gian thực hiện toàn bộ 50000 truy vấn. Bạn sẽ thấy tổng thời gian này cũng rất nhỏ.
Thêm một đoạn code đo thời gian cho một truy vấn sử dụng cách naive. Bạn sẽ thấy thời gian cho một truy vấn naive có thể lớn hơn tổng thời gian cho 50000 truy vấn dùng prefix sum, tùy thuộc vào kích thước đoạn truy vấn naive. Điều này làm nổi bật hiệu quả của kỹ thuật mảng cộng dồn khi có nhiều truy vấn.

Comments

There are no comments at the moment.