Tutorial — Đếm Đoạn

Tổng số ký tự `1` trong một đoạn con liên tiếp có thể được tính bằng hiệu giữa tổng số ký tự `1` của hai tiền tố. Việc tính trực tiếp số ký tự `1` cho mọi đoạn con bằng hai vòng lặp sẽ tốn thời gian $O(n^2)$ và bị quá thời gian.

Nếu cố định vị trí kết thúc $j$ của đoạn con và gọi $p_j$ là tổng tiền tố số lượng ký tự `1` đến vị trí $j$, điều kiện đoạn con từ $i$ đến $j$ có đúng $k$ ký tự `1` trở thành $p_{i-1} = p_j - k$. Do đó, tại mỗi $j$, ta chỉ cần đếm số vị trí $i-1 < j$ có giá trị $p_{i-1}$ bằng $p_j - k$.

Ta sử dụng phương pháp tổng tiền tố kết hợp mảng đếm tần suất để lưu lại số lần xuất hiện của các giá trị $p_x$ với $x < j$. Khi duyệt qua từng vị trí $j$, ta cộng $\text{cnt}[p_j - k]$ vào đáp án rồi cập nhật $\text{cnt}[p_j]$ trong thời gian $O(1)$ mỗi bước.