Một mảng prefix sum (tổng tiền tố) lưu các tổng tích lũy để bất kỳ tổng khoảng nào cũng có thể được trả lời trong O(1) sau khi tiền xử lý O(n) — thay vì O(n) mỗi truy vấn.
Ý tưởng
Gọi là tổng của phần tử đầu tiên. Khi đó tổng của là .
Một mảng prefix sum (tổng tiền tố) lưu các tổng tích lũy để bất kỳ tổng khoảng nào cũng có thể được trả lời trong O(1) sau khi tiền xử lý O(n) — thay vì O(n) mỗi truy vấn.
Gọi là tổng của phần tử đầu tiên. Khi đó tổng của là .
prefix[i]iarr[l..r]prefix[r+1] - prefix[l]def build_prefix(arr):
prefix = [0] * (len(arr) + 1)
for i, x in enumerate(arr):
prefix[i + 1] = prefix[i] + x # tổng chạy
return prefix
def range_sum(prefix, l, r): # bao gồm cả l..r
return prefix[r + 1] - prefix[l] # O(1)
p = build_prefix([2, 4, 1, 3, 5])
range_sum(p, 1, 3) # 4+1+3 -> 8
arr = [2, 4, 1, 3, 5]
prefix = [0, 2, 6, 7, 10, 15]
sum(1..3) = prefix[4] - prefix[1] = 10 - 2 = 8
Lý tưởng cho nhiều truy vấn tổng khoảng trên dữ liệu tĩnh. Các biến thể: prefix sum 2D cho tổng ma trận con, prefix XOR, và mảng hiệu (difference array) cho cập nhật khoảng. Nếu mảng thay đổi thường xuyên, hãy dùng Fenwick/segment tree thay thế. Cẩn thận với độ lệch chỉ số (kích thước n+1).
Prefix sum biến các truy vấn khoảng O(n) lặp lại thành các phép tra cứu O(1) — một thắng lợi lớn khi truy vấn diễn ra thường xuyên.
Mô thức tính-trước-một-lần, trả-lời-nhanh khái quát hóa cho nhiều tác vụ xử lý dữ liệu.
Đây là một thành phần chủ lực trong lập trình thi đấu và một khối xây dựng phổ biến trong phân tích dữ liệu (analytics).
Thư viện câu hỏi phỏng vấn IT với đáp án chi tiết — từ Junior đến Senior.
Ủng hộ