Prefix Sum (Tổng tiền tố) — Prefix Sum
Prefix sum (tổng tiền tố) là mảng phụ prefix trong đó prefix[i] = tổng của i phần tử đầu tiên, với quy ước prefix[0] = 0. Xây một lần bằng một vòng lặp O(n).
Khi đã có mảng tiền tố, tổng của đoạn bất kỳ [l, r] tính được ngay: prefix[r + 1] − prefix[l] — mỗi truy vấn chỉ tốn O(1) thay vì cộng lại từ đầu.
Biến thể quan trọng: kết hợp với Hash Map để đếm số đoạn con có tổng bằng K — vừa quét vừa lưu số lần mỗi giá trị tiền tố đã xuất hiện; đoạn con kết thúc tại vị trí hiện tại có tổng K khi và chỉ khi tồn tại tiền tố trước đó bằng sum − K. Cách này chạy đúng cả khi mảng có số âm — trường hợp mà Sliding Window không xử lý được.
Như cột số km trên quốc lộ — mỗi cột ghi quãng đường tính từ điểm xuất phát.
- Muốn biết đoạn giữa km 120 và km 350 dài bao nhiêu, chỉ cần lấy 350 trừ 120, không phải đi đo lại từng mét.
- Tính trước một lần, tra cứu mãi mãi.
Dấu hiệu nhận biết
Gặp những từ khoá này trong đề → nghĩ ngay đến Prefix Sum (Tổng tiền tố)
| Từ khoá trong đề | Tại sao gợi đến chủ đề này |
|---|---|
| tổng đoạn [l, r] nhiều lần | Tính trước tổng tiền tố, mỗi truy vấn còn O(1) |
| đếm subarray có tổng = K | Prefix sum + Hash Map đếm tiền tố đã gặp |
| mảng có số âm | Sliding Window không áp dụng được — tổng không đơn điệu |
| tích/tổng trừ phần tử hiện tại | Kết hợp quét tiền tố từ trái và hậu tố từ phải |
Khi nào dùng
4 tình huống điển hình cần nghĩ đến chủ đề này
Nhiều truy vấn tổng đoạn [l, r] trên mảng không thay đổi
Đếm / tìm đoạn con có tổng bằng K, chia hết cho K, hoặc thỏa điều kiện trên tổng (kết hợp Hash Map)
Mảng có số âm khiến Sliding Window không áp dụng được
Bài 2 chiều: tổng vùng chữ nhật trong ma trận (prefix sum 2D)
Tích tiền tố / hậu tố — cùng ý tưởng nhưng thay phép cộng bằng phép nhân
Khi nào KHÔNG dùng
3 tình huống chủ đề này không phù hợp — biết để tránh overuse
Mảng bị cập nhật thường xuyên: mỗi lần sửa một phần tử phải xây lại toàn bộ mảng tiền tố — cần Fenwick tree / Segment tree
Chỉ truy vấn đúng 1 lần: cộng trực tiếp O(n) là đủ, xây mảng tiền tố không giúp gì thêm
Cần min / max của đoạn thay vì tổng: phép min/max không có phép trừ ngược, dùng Sparse Table hoặc Segment tree
Code mẫu
Hầu hết bài cùng chủ đề dùng chung mẫu này — copy rồi điền phần logic riêng của bài.
function prefixSumPattern(nums: number[]): R {
// prefix[i] = tổng nums[0..i-1]; prefix[0] = 0
const prefix = new Array(nums.length + 1).fill(0)
for (let i = 0; i < nums.length; i++) {
prefix[i + 1] = prefix[i] + nums[i]
}
// Tổng đoạn [l, r] = prefix[r + 1] - prefix[l] — O(1) mỗi truy vấn
return answerQueries(prefix)
}Recap
Tổng hợp nhanh — đọc lại trước phỏng vấn
Điểm chính
prefix[0] = 0, prefix[i] = prefix[i−1] + nums[i−1] — mảng tiền tố dài n+1 để không phải xử lý case riêng
Tổng đoạn [l, r] = prefix[r + 1] − prefix[l]
Đếm đoạn con tổng bằng K: Hash Map lưu số lần mỗi tiền tố xuất hiện, tra sum − K tại từng bước
Có số âm vẫn đúng — đây là lợi thế so với Sliding Window
Lỗi thường gặp
Lệch chỉ số vì quên quy ước prefix[0] = 0 (mảng tiền tố phải dài n+1)
Dùng Sliding Window cho bài tổng bằng K khi mảng có số âm — cửa sổ co giãn sai vì tổng không còn đơn điệu
Quên khởi tạo map.set(0, 1) (tiền tố rỗng) → bỏ sót các đoạn con bắt đầu từ chỉ số 0
Độ phức tạp
tiền xử lý O(n), mỗi truy vấn O(1)Bài luyện theo chủ đề này
Phân theo độ khó — luyện tuần tự cho chắc tay