Chủ đề 18 trong bảng đặc tả đề thi HSG lớp 12 môn Tin học: Tổng tiền tố.

Yêu cầu cần đạt:

• Biết: Định nghĩa ; công thức nhanh ; chỉ số bắt đầu từ 0 hoặc 1; tính P trong O(N).
• Hiểu: Thiết kế tiền tố cho nhiều đại lượng (tổng, đếm điều kiện, XOR tiền tố); lựa chọn kiểu số an toàn (64‑bit); tổ chức tiền tố nhiều mảng/nhóm; mở rộng tiền tố 2D cho truy vấn hình chữ nhật.
• Vận dụng: Trả lời truy vấn đoạn số lượng lớn; đếm số đoạn con có tổng = S bằng map tần suất tiền tố; đếm chia hết theo modulo (tiền tố đồng dư M); phối hợp với two‑pointers/cửa sổ để đạt O(N) khi đủ điều kiện.

Các bài được lấy từ đề thi thật (nhóm THITHAT) và xếp từ dễ đến khó.