Nguồn: CSES
Gọi 
~s(i)~ là tổng tiền tố (prefix sum): 
~s(i)=a_1+a_2+...+a_i~. Sử dụng hàm này, ta có thể tính tổng của một đoạn con bất kỳ như sau:
$$\displaystyle a_l+a_{l+1}+...+a_r=s(r)-s(l-1)$$
Để tính số lượng đoạn con kết thúc tại vị trí 
~i~ và có tổng bằng 
~x~, ta cần tìm tất cả các giá trị 
~j < i~ sao cho:
$$\displaystyle s(i)-s(j)=x$$
, điều này tương đương với:
$$\displaystyle s(j)=s(i)-x$$
Ta có thể lưu số lần xuất hiện của mỗi giá trị tổng tiền tố đã gặp trước đó. Khi xét vị trí ~i~, chỉ cần kiểm tra xem giá trị 
~s(i) - x~ đã xuất hiện bao nhiêu lần, từ đó nhanh chóng xác định được số lượng đoạn con cần tìm.
Có thể sử dụng cấu trúc map để đếm số lần xuất hiện của các tổng tiền tố.
Độ phức tạp: 
~O(n.log(n))~
Bình luận