Khi luyện thi Chuyên Tin, bài toán tính tổng nhiều đoạn xuất hiện thường xuyên. Với mỗi truy vấn, nếu cộng lại từng phần tử từ đầu, chương trình có thể chạy chậm. Mảng cộng dồn, hay prefix sum, giúp trả lời mỗi truy vấn tổng đoạn trong thời gian hằng số sau một lượt chuẩn bị.
Bài viết dành cho học sinh THCS, THPT tại Kiến An và Hải Phòng đã biết mảng, vòng lặp và kiểu số nguyên trong C++.
Bài toán tổng đoạn
Cho mảng gồm n số nguyên và q truy vấn. Mỗi truy vấn gồm hai chỉ số l, r theo cách đánh số từ 1. Hãy tính tổng các phần tử từ l đến r, kể cả hai đầu.
Ví dụ mảng 2, -1, 3, 5, 4: tổng đoạn từ vị trí 2 đến 4 là -1 + 3 + 5 = 7. Giả sử đầu vào hợp lệ: 1 <= l <= r <= n.
Cách trực tiếp duyệt từng đoạn mất tối đa O(n) cho mỗi truy vấn, tức O(nq) trong trường hợp xấu nhất. Khi n và q lớn, ta cần cách tốt hơn.
Công thức mảng cộng dồn
Đặt prefix[0] = 0. Với mỗi vị trí i từ 1 đến n, định nghĩa prefix[i] = prefix[i - 1] + a[i]. Khi đó prefix[i] là tổng từ phần tử đầu tiên đến phần tử thứ i.
Với mảng ví dụ, các giá trị prefix lần lượt là 0, 2, 1, 4, 9, 13. Muốn lấy tổng đoạn [l, r], ta lấy tổng đến r trừ phần đứng trước l:
sum(l, r) = prefix[r] - prefix[l - 1]Chẳng hạn sum(2, 4) = prefix[4] - prefix[1] = 9 - 2 = 7. Công thức vẫn đúng khi có số âm và khi l = 1, nhờ prefix[0] = 0.
Cài đặt C++ và kiểm tra kết quả
Chương trình sau đọc n q, tiếp theo là n phần tử và q cặp l r:
#include <iostream>
#include <vector>
using namespace std;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n, q;
cin >> n >> q;
vector<long long> prefix(n + 1, 0);
for (int i = 1; i <= n; ++i) {
long long x;
cin >> x;
prefix[i] = prefix[i - 1] + x;
}
while (q--) {
int l, r;
cin >> l >> r;
cout << prefix[r] - prefix[l - 1] << '\n';
}
return 0;
}Dữ liệu mẫu:
5 3
2 -1 3 5 4
2 4
1 5
3 3Kết quả:
7
13
3Lưu mã vào main.cpp, biên dịch và chạy bằng g++ -std=c++17 -O2 -Wall -Wextra main.cpp -o main rồi ./main. Hãy nhập dữ liệu mẫu và so sánh ba dòng kết quả. Với Windows, có thể chạy main.exe tùy môi trường.
Thời gian dựng mảng là O(n), mỗi truy vấn là O(1), tổng cộng O(n + q); bộ nhớ là O(n). Dùng long long để tăng miền biểu diễn, nhưng vẫn phải kiểm tra giới hạn đề bài để bảo đảm cả tổng nằm trong phạm vi kiểu dữ liệu.
Những lỗi thường gặp
- Nhầm chỉ số từ 0 và từ 1: trong cách viết này, truy vấn dùng chỉ số từ 1.
- Trừ
prefix[l]thay vìprefix[l - 1]: làm mất phần tử ở vị tríl. - Bỏ quên trường hợp
l = 1: cần phần tử gốcprefix[0] = 0. - Dùng
intcho tổng lớn: kể cả khi từng phần tử vừaint, tổng có thể vượt giới hạn. - Dùng prefix sum tĩnh cho mảng liên tục thay đổi: mỗi lần sửa một phần tử có thể phải cập nhật nhiều prefix; hãy cân nhắc Fenwick tree hoặc segment tree khi bài yêu cầu cập nhật và truy vấn xen kẽ.
Bài tập tự luyện
- Với mảng
4, -2, 7, 0, tính tổng các đoạn[1, 1],[2, 3]và[1, 4]. Đáp án lần lượt là4,5,9. - Viết chương trình đếm tổng số phần tử chẵn trong từng đoạn: chuyển mỗi phần tử chẵn thành 1, phần tử lẻ thành 0 rồi áp dụng prefix sum.
- Tạo mảng nhỏ ngẫu nhiên có số âm; với mọi
l, rhợp lệ, so sánh kết quả prefix sum với cách cộng trực tiếp. Đây là cách kiểm tra lỗi biên trước khi nộp bài.
Để đọc thêm về các kiểu số nguyên và container sử dụng trong ví dụ, xem tài liệu kiểu số nguyên C++ và std::vector . Bài liên quan: Tìm kiếm nhị phân C++ cho học sinh luyện thi Chuyên Tin.
Học Chuyên Tin tại Kiến An
Nếu cần một lộ trình luyện thuật toán C++ và được góp ý cách trình bày lời giải, phụ huynh và học sinh có thể liên hệ VCoderLog để tìm hiểu lớp Chuyên Tin. Phòng Lab tại 261 Phan Đăng Lưu, Kiến An, Hải Phòng; học viên mang laptop cá nhân khi thực hành. Hãy hỏi trực tiếp để xác nhận lịch và tình trạng lớp hiện tại.

