Chào mừng các bạn quay trở lại với series bài viết về C++! Hôm nay chúng ta sẽ cùng tìm hiểu một kỹ thuật xử lý mảng cực kỳ phổ biến và hiệu quả, đặc biệt hữu ích trong các bài toán cần tính toán tổng của các đoạn con trong mảng một cách nhanh chóng. Đó chính là kỹ thuật Mảng cộng dồn, hay còn gọi là Prefix Sum Array.

Mảng cộng dồn là gì?

Hãy tưởng tượng bạn có một mảng số nguyên arr và bạn được yêu cầu tính tổng của các phần tử trong rất nhiều đoạn con khác nhau của mảng. Ví dụ, tính tổng từ chỉ mục 2 đến 5, rồi lại từ chỉ mục 0 đến 3, rồi từ 7 đến 9,... Nếu mỗi lần truy vấn bạn lại duyệt qua từng phần tử trong đoạn đó để tính tổng (cách "ngây thơ"), thì với mỗi truy vấn, độ phức tạp thời gian sẽ là O(độ dài đoạn). Nếu có nhiều truy vấn trên các đoạn dài, tổng thời gian sẽ trở nên rất lớn.

Kỹ thuật mảng cộng dồn ra đời để giải quyết vấn đề này. Thay vì tính toán lại tổng cho mỗi truy vấn, chúng ta sẽ tiền xử lý (pre-process) mảng gốc để tạo ra một mảng mới - mảng cộng dồn prefix_sum. Mảng prefix_sum này có một tính chất đặc biệt: phần tử tại chỉ mục i của nó sẽ lưu trữ tổng của tất cả các phần tử từ chỉ mục 0 đến chỉ mục i của mảng gốc.

Cụ thể, nếu mảng gốc là arr có n phần tử (đánh số từ 0 đến n-1), mảng cộng dồn prefix_sum (thường có kích thước n+1 để tiện tính toán) sẽ được xây dựng như sau:

prefix_sum[0] = 0
prefix_sum[1] = arr[0]
prefix_sum[2] = arr[0] + arr[1]
prefix_sum[3] = arr[0] + arr[1] + arr[2]
...
prefix_sum[i] = arr[0] + arr[1] + ... + arr[i-1] (với i từ 1 đến n)

Công thức truy hồi để xây dựng mảng cộng dồn một cách hiệu quả là: prefix_sum[i] = prefix_sum[i-1] + arr[i-1] (với i từ 1 đến n)

Xây dựng mảng cộng dồn trong C++

Chúng ta sẽ bắt đầu bằng việc xây dựng mảng cộng dồn từ một mảng gốc cho trước.

Ví dụ 1: Xây dựng mảng cộng dồn cho mảng arr = {1, 2, 3, 4, 5}.

Mảng gốc arr có kích thước n = 5. Chúng ta sẽ tạo mảng cộng dồn prefix_sum có kích thước n+1 = 6.

prefix_sum[0] = 0 (theo định nghĩa)
prefix_sum[1] = prefix_sum[0] + arr[0] = 0 + 1 = 1
prefix_sum[2] = prefix_sum[1] + arr[1] = 1 + 2 = 3
prefix_sum[3] = prefix_sum[2] + arr[2] = 3 + 3 = 6
prefix_sum[4] = prefix_sum[3] + arr[3] = 6 + 4 = 10
prefix_sum[5] = prefix_sum[4] + arr[4] = 10 + 5 = 15

Mảng cộng dồn thu được sẽ là prefix_sum = {0, 1, 3, 6, 10, 15}.

Đây là code C++ để thực hiện việc này:

#include <iostream>
#include <vector>
#include <numeric> // Bao gồm một số hàm hữu ích, nhưng không bắt buộc cho việc xây dựng cơ bản

int main() {
    // Mảng gốc
    vector<int> arr = {1, 2, 3, 4, 5};
    int n = arr.size();

    // Khai báo mảng cộng dồn có kích thước n+1 và khởi tạo tất cả bằng 0
    // prefix_sum[i] sẽ lưu tổng arr[0]...arr[i-1]
    vector<int> prefix_sum(n + 1, 0);

    // Xây dựng mảng cộng dồn
    // prefix_sum[i] = prefix_sum[i-1] + arr[i-1]
    for (int i = 0; i < n; ++i) {
        prefix_sum[i + 1] = prefix_sum[i] + arr[i];
    }

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

    cout << "Mang cong don (size n+1): ";
    for (int x : prefix_sum) {
        cout << x << " ";
    }
    cout << endl;

    return 0;
}

Giải thích code:

Chúng ta dùng vector để biểu diễn mảng. vector linh hoạt và dễ sử dụng.
vector<int> prefix_sum(n + 1, 0); tạo một vector có kích thước n+1 và khởi tạo tất cả các phần tử bằng 0. prefix_sum[0] bằng 0 là điểm mấu chốt để công thức truy vấn sau này được đơn giản.
Vòng lặp for (int i = 0; i < n; ++i) duyệt qua các phần tử của mảng arr (từ arr[0] đến arr[n-1]).
Trong mỗi lần lặp, chúng ta tính prefix_sum[i + 1] dựa trên prefix_sum[i] (tổng đến arr[i-1]) cộng thêm arr[i] hiện tại. Điều này đảm bảo prefix_sum[i+1] chứa tổng của arr[0] đến arr[i].
Thời gian để xây dựng mảng cộng dồn là O(n), chỉ cần duyệt mảng gốc một lần.

Truy vấn tổng đoạn con nhanh chóng

Đây là lúc mảng cộng dồn thể hiện sức mạnh. Giả sử bạn muốn tính tổng của đoạn con từ chỉ mục l đến r (bao gồm cả arr[l] và arr[r], với l và r là chỉ mục 0-based trong mảng gốc arr).

Tổng của đoạn arr[l...r] chính là: (arr[0] + ... + arr[r]) - (arr[0] + ... + arr[l-1])

Nhìn vào định nghĩa của mảng cộng dồn prefix_sum (kích thước n+1), chúng ta có:

(arr[0] + ... + arr[r]) chính là prefix_sum[r + 1]
(arr[0] + ... + arr[l-1]) chính là prefix_sum[l]

Vậy, tổng của đoạn con từ chỉ mục l đến r trong mảng gốc arr (0-indexed) sẽ là: sum(l, r) = prefix_sum[r + 1] - prefix_sum[l]

Công thức này hoạt động ngay cả khi l = 0, vì khi đó prefix_sum[l] là prefix_sum[0], giá trị này đã được khởi tạo là 0, và prefix_sum[r+1] - 0 = prefix_sum[r+1], đúng bằng tổng từ arr[0] đến arr[r].

Ví dụ 2: Sử dụng mảng cộng dồn để tính tổng các đoạn con. Sử dụng mảng gốc arr = {1, 2, 3, 4, 5} và mảng cộng dồn prefix_sum = {0, 1, 3, 6, 10, 15} đã xây dựng ở trên.

Truy vấn 1: Tính tổng đoạn từ chỉ mục 2 đến 4 (l=2, r=4). Đoạn này gồm arr[2], arr[3], arr[4].
- Tổng = arr[2] + arr[3] + arr[4] = 3 + 4 + 5 = 12.
- Sử dụng công thức mảng cộng dồn: sum(2, 4) = prefix_sum[4 + 1] - prefix_sum[2] = prefix_sum[5] - prefix_sum[2] = 15 - 3 = 12. (Kết quả khớp!)
Truy vấn 2: Tính tổng đoạn từ chỉ mục 0 đến 3 (l=0, r=3). Đoạn này gồm arr[0], arr[1], arr[2], arr[3].
- Tổng = arr[0] + arr[1] + arr[2] + arr[3] = 1 + 2 + 3 + 4 = 10.
- Sử dụng công thức mảng cộng dồn: sum(0, 3) = prefix_sum[3 + 1] - prefix_sum[0] = prefix_sum[4] - prefix_sum[0] = 10 - 0 = 10. (Kết quả khớp!)

Đây là code C++ minh họa cách thực hiện truy vấn sau khi đã có mảng cộng dồn:

#include <iostream>
#include <vector>

int main() {
    vector<int> arr = {1, 2, 3, 4, 5};
    int n = arr.size();

    // Xây dựng mảng cộng dồn (như ở ví dụ 1)
    vector<int> prefix_sum(n + 1, 0);
    for (int i = 0; i < n; ++i) {
        prefix_sum[i + 1] = prefix_sum[i] + arr[i];
    }

    // --- Thực hiện các truy vấn tổng đoạn con ---

    // Truy vấn 1: Tổng từ chỉ mục 2 đến 4 (0-indexed)
    int l1 = 2, r1 = 4;
    // Công thức: sum(l, r) = prefix_sum[r + 1] - prefix_sum[l]
    int sum1 = prefix_sum[r1 + 1] - prefix_sum[l1];
    cout << "Tong doan arr[" << l1 << ".." << r1 << "] la: " << sum1 << endl;

    // Truy vấn 2: Tổng từ chỉ mục 0 đến 3 (0-indexed)
    int l2 = 0, r2 = 3;
    int sum2 = prefix_sum[r2 + 1] - prefix_sum[l2];
    cout << "Tong doan arr[" << l2 << ".." << r2 << "] la: " << sum2 << endl;

    // Truy vấn 3: Tổng từ chỉ mục 1 đến 1 (tức là chính arr[1])
    int l3 = 1, r3 = 1;
    int sum3 = prefix_sum[r3 + 1] - prefix_sum[l3];
    cout << "Tong doan arr[" << l3 << ".." << r3 << "] la: " << sum3 << endl; // Expected: arr[1] = 2

    return 0;
}

Giải thích code:

Phần đầu code vẫn xây dựng mảng prefix_sum như trước.
Với mỗi truy vấn, chúng ta chỉ cần biết chỉ mục bắt đầu (l) và kết thúc (r) của đoạn con trong mảng gốc.
Áp dụng công thức prefix_sum[r + 1] - prefix_sum[l]. Việc truy cập các phần tử trong mảng chỉ mất thời gian O(1).
Thời gian để trả lời mỗi truy vấn chỉ là O(1), sau khi đã có mảng cộng dồn.

So sánh hiệu quả

Cách "ngây thơ" (duyệt trực tiếp): Để trả lời Q truy vấn tổng đoạn con, mỗi truy vấn mất O(N) (trong trường hợp xấu nhất là đoạn dài gần hết mảng). Tổng thời gian là O(Q * N).
Cách dùng mảng cộng dồn: Mất O(N) để tiền xử lý (xây dựng mảng cộng dồn). Sau đó, mỗi truy vấn chỉ mất O(1). Tổng thời gian là O(N + Q).

Rõ ràng, khi số lượng truy vấn Q lớn hơn nhiều so với N, kỹ thuật mảng cộng dồn mang lại hiệu quả vượt trội. Đây là lý do nó được sử dụng rộng rãi trong lập trình thi đấu và các bài toán thực tế cần xử lý nhanh các truy vấn tổng trên đoạn.

Comments

There are no comments at the moment.