Level 1 · Cơ bản

Prefix sum

Tổng tiền tố và mảng hiệu (difference array).

Trung bình Visualizer tương tác8 bài luyện tập

Ý tưởng chính

Prefix sum cho phép truy vấn tổng một đoạn trong O(1) sau khi tiền xử lý O(n), là nền tảng cho nhiều bài toán truy vấn đoạn.

Hình dung

Đồng hồ công-tơ-mét xe máy ghi tổng số km từ lúc mua. Muốn biết hôm nay đi bao xa, chỉ cần lấy số tối nay trừ số sáng nay, không phải cộng lại từng chuyến.

Cách hoạt động

1
Tạo mảng prefix với prefix[0] = 0 và prefix[i + 1] = prefix[i] + arr[i].
2
Tổng đoạn [l, r] = prefix[r + 1] − prefix[l], tính ngay trong O(1).
3
Mảng hiệu (ngược lại): muốn cộng d vào cả đoạn [l, r], chỉ cần diff[l] += d và diff[r + 1] −= d.
4
Sau khi xử lý hết các lần cộng, lấy prefix sum của diff là ra mảng kết quả.

Độ phức tạp

Xây O(n), mỗi truy vấn tổng đoạn O(1). Mảng hiệu: mỗi lần cập nhật đoạn O(1), khôi phục O(n).

Khi nào dùng

Có nhiều truy vấn tổng đoạn trên mảng không đổi, hoặc nhiều lần cộng giá trị cho cả đoạn rồi mới hỏi kết quả cuối.

Lỗi hay gặp

Lệch chỉ số: nhầm prefix[r] với prefix[r + 1].
Tràn số int khi cộng dồn nhiều số lớn — dùng long long.
Mảng bị cập nhật xen kẽ với truy vấn: prefix sum tĩnh không còn đúng, cần Fenwick tree.

Liên hệ thực tế

Ứng dụng thực tế

Kỹ thuật này xuất hiện ở đâu ngoài đời — để bạn có sẵn một hình ảnh cụ thể khi học.

Báo cáo doanh thu theo khoảng ngày
Tính sẵn doanh thu cộng dồn một lần, sau đó tổng từ ngày l đến ngày r bất kỳ chỉ là một phép trừ.
Xử lý ảnh: ảnh tích phân
Summed-area table cho tổng độ sáng một vùng chữ nhật bất kỳ trong O(1); bộ phát hiện khuôn mặt Viola–Jones dựa trên kỹ thuật này.
Đặt phòng khách sạn, lịch sự kiện
Mảng hiệu: mỗi lượt đặt cộng +1 ở ngày nhận, −1 sau ngày trả, cộng dồn một lần là biết số phòng dùng mỗi ngày.
Số liệu tích luỹ
Bước chân trong tuần, lượng mưa từ đầu mùa, số ca mắc cộng dồn — đều là prefix sum của dữ liệu theo ngày.

Xem thuật toán chạy

Minh hoạ từng bước

Chạy tự động hoặc đi từng bước; theo dõi hình minh hoạ, lời giải thích, giá trị biến và dòng code tương ứng cùng lúc.

Bấm vào khung minh hoạ, rồi:Space chạy / dừng←→ từng bướcHomeEnd đầu / cuối

Tự làm

Luyện tập trên Codeforces

Sắp xếp từ dễ đến khó theo rating, mỗi bài kèm tóm tắt đề. Bí thì mở gợi ý — có 3 mức, từ hướng suy nghĩ tới gần lời giải.

Rating 900
Odd Queries(mở Codeforces trong tab mới)
Cho mảng a và q truy vấn độc lập (l, r, k): nếu thay mọi phần tử a_l..a_r bằng k thì tổng cả mảng có lẻ không (YES/NO).
Test mẫu & giải thích
Input
2 5 5 2 2 1 3 2 2 3 3 2 3 4 1 5 5 1 4 9 2 4 3 10 5 1 1 1 1 1 1 1 1 1 1 3 8 13 2 5 10 3 8 10 1 10 2 1 9 100
Output
YES YES YES NO YES NO NO NO NO YES
Test 1
Mảng a = [2,2,1,3,2] có tổng ban đầu là 10. Truy vấn "2 3 3": thay a2, a3 (đang là 2 và 1) bằng 3 thì mảng thành [2,3,3,3,2], tổng 13 là số lẻ nên in YES.
Test 2
Truy vấn "1 4 9": thay a1..a4 bằng 9 thì mảng thành [9,9,9,9,2], tổng 38 là số chẵn nên in NO.
Rating 1200
XXXXX(mở Codeforces trong tab mới)
Cho mảng a và số x. Tìm độ dài đoạn con liên tiếp dài nhất có tổng không chia hết cho x, hoặc −1 nếu không có.
Test mẫu & giải thích
Input
3 3 3 1 2 3 3 4 1 2 3 2 2 0 6
Output
2 3 -1
Test 1
Với a=[1,2,3], x=3: tổng cả mảng là 6 chia hết cho 3 nên không thể lấy nguyên cả mảng. Phần tử a1=1 không chia hết cho 3, bỏ nó đi thì đoạn còn lại [2,3] có tổng 5 không chia hết cho 3, độ dài 2; đây là độ dài lớn nhất có thể đạt được nên đáp án là 2.
Test 2
Với a=[1,2,3], x=4: tổng 6 chia 4 dư 2 (không chia hết) nên lấy nguyên cả mảng độ dài 3 luôn thoả, đáp án 3.
Test 3
Với a=[0,6], x=2: mọi phần tử đều chia hết cho 2 nên mọi đoạn con đều có tổng chia hết cho 2, không có đoạn nào thoả, đáp án -1.
Rating 1200
Prefix Sum Addicts(mở Codeforces trong tab mới)
Có một dãy n số nguyên không giảm, nhưng bạn chỉ biết k tổng tiền tố cuối cùng s_{n−k+1}, …, s_n. Hỏi có tồn tại dãy như vậy không.
Test mẫu & giải thích
Input
4 5 5 1 2 3 4 5 7 4 -6 -5 -3 0 3 3 2 3 4 3 2 3 4
Output
Yes Yes No No
Test 1
Test đầu n=5,k=5 biết đủ cả 5 tổng tiền tố [1,2,3,4,5], suy ra a1=s1=1 và các a_i=s_i-s_{i-1}=1 với i=2..5, dãy [1,1,1,1,1] không giảm nên hợp lệ, in Yes.
Test 2
Test thứ ba n=3,k=3 biết cả s1,s2,s3=[2,3,4], nên a1=s1=2 bị cố định, còn a2=s2-s1=1, a3=s3-s2=1; nhưng a1=2 > a2=1 vi phạm tính không giảm nên in No.
Test 3
Test thứ tư n=3,k=2 chỉ biết s2=3,s3=4 nên a3=s3-s2=1 xác định, còn a1,a2 chưa biết nhưng phải không giảm và đều không vượt quá a3=1, tức tổng a1+a2 tối đa là 1+1=2; mà a1+a2 phải bằng s2=3>2 nên vô lý, in No.
Rating 1500
Polycarp and Div 3(mở Codeforces trong tab mới)
Cho số nguyên s rất dài. Cắt s thành các phần (không có số 0 vô nghĩa ở đầu, trừ chính số 0) sao cho số phần chia hết cho 3 là nhiều nhất.
Test mẫu & giải thích
Input
3121
Output
2
Với s="3121", cắt thành "3", "12", "1": phần "3" chia hết cho 3, phần "12" chia hết cho 3 (12/3=4), phần "1" thì không, tổng cộng có 2 phần chia hết cho 3. Không thể đạt 3 hay 4 phần chia hết cho 3 vì tổng các chữ số của cả chuỗi là 3+1+2+1=7 không chia hết cho 3, nên không thể chia toàn bộ 4 chữ số riêng lẻ mà tất cả đều chia hết cho 3, và các cách cắt khác cũng không vượt quá 2. Do đó đáp án là 2.
Rating 1600
Good Subarrays(mở Codeforces trong tab mới)
Cho mảng các chữ số a. Đếm số đoạn con [l, r] có tổng các phần tử đúng bằng độ dài đoạn (r − l + 1).
Test mẫu & giải thích
Input
3 3 120 5 11011 6 600005
Output
3 6 1
Test 1
Với a=[1,2,0], xét mọi đoạn con: "1" (tổng 1, dài 1) ✓, "2" ✗, "0" ✗, "12" (tổng 3, dài 2) ✗, "20" (tổng 2, dài 2) ✓, "120" (tổng 3, dài 3) ✓. Có 3 đoạn tốt.
Test 2
Với a=[1,1,0,1,1]: bốn đoạn "1" dài 1 đều tốt; hai đoạn "11" (vị trí 1–2 và 4–5) có tổng 2 bằng độ dài; các đoạn còn lại như "110", "1101", "11011" đều có tổng nhỏ hơn độ dài. Tổng cộng 4 + 2 = 6.
Rating 1600
Least Prefix Sum(mở Codeforces trong tab mới)
Cho mảng a và vị trí m. Mỗi thao tác đổi dấu một phần tử. Tìm số thao tác ít nhất để tổng tiền tố thứ m là nhỏ nhất trong mọi tổng tiền tố.
Test mẫu & giải thích
Input
6 4 3 -1 -2 -3 -4 4 3 1 2 3 4 1 1 1 5 5 -2 3 -5 1 -20 5 2 -2 3 -5 -5 -20 10 4 345875723 -48 384678321 -375635768 -35867853 -35863586 -358683842 -81725678 38576 -357865873
Output
1 1 0 0 3 4
Test 1
Với a=[-1,-2,-3,-4], m=3: tổng tiền tố gốc là -1,-3,-6,-10; P3=-6 chưa phải nhỏ nhất vì P4=-10<P3. Đổi dấu a4 thành +4 thì P4 mới = -6+4=-2 ≥ P3=-6, còn P1,P2 không đổi vẫn ≥ -6, chỉ cần 1 lần đổi dấu nên đáp án là 1.
Test 2
Với a=[1,2,3,4], m=3: tổng tiền tố gốc 1,3,6,10, P3=6 không nhỏ nhất vì P1=1<6; đổi dấu a3 thành -3 cho tổng tiền tố mới là 1,3,0,4, lúc này P3=0 là nhỏ nhất trong tất cả, cũng chỉ cần 1 lần đổi dấu, đáp án 1.
Rating 1600
Zero-Sum Prefixes(mở Codeforces trong tab mới)
Cho mảng a. Mỗi phần tử bằng 0 có thể được thay bằng số nguyên bất kỳ. Tìm số lượng lớn nhất các tổng tiền tố bằng 0.
Test mẫu & giải thích
Input
5 5 2 0 1 -1 0 3 1000000000 1000000000 0 4 0 0 0 0 8 3 0 2 -10 10 -30 30 0 9 1 0 0 1 -1 0 1 0 -1
Output
3 1 4 4 5
Test 1
Với a=[2,0,1,-1,0], hai vị trí 2 và 5 là các phần tử 0 có thể gán giá trị tuỳ ý. Chọn a2=-2 để tổng tiền tố tại vị trí 2 bằng 0; đoạn tiếp theo a3=1, a4=-1 cố định nên tổng tiền tố tại vị trí 3 là 0+1=1 (chưa về 0) nhưng tại vị trí 4 là 1-1=0 (tự nhiên quay về 0). Vị trí 5 là số 0 cuối cùng nên luôn chọn được giá trị để tổng tiền tố tại đó lại bằng 0. Tổng cộng có 3 vị trí đạt tổng tiền tố 0 (vị trí 2, 4, 5), khớp đáp án 3.
Test 2
Với a=[1000000000,1000000000,0], hai phần tử đầu cố định dương nên tổng tiền tố tại đó luôn khác 0, chỉ vị trí 3 (số 0) có thể chọn giá trị -2×10^9 để đưa tổng về 0, cho đáp án 1.
Rating 1700
Number of Ways(mở Codeforces trong tab mới)
Cho mảng a. Đếm số cách chia mảng thành 3 đoạn liên tiếp không rỗng có tổng bằng nhau.
Test mẫu & giải thích
Input
5 1 2 3 0 3
Output
2
Với a=[1,2,3,0,3], tổng cả mảng là 9 nên mỗi phần phải có tổng 3. Tổng tiền tố lần lượt là P1=1, P2=3, P3=6, P4=6, P5=9; cần điểm cắt i với Pi=3 (chỉ tại i=2) và điểm cắt j>i với Pj=6 (=2*3, đạt tại j=3 hoặc j=4). Cả hai giá trị j=3 và j=4 đều lớn hơn i=2 nên có 2 cách chia: (1,2)|(3)|(4,5) và (1,2)|(3,4)|(5), mỗi đoạn đều có tổng 3, khớp đáp án 2.