Editorial for Tổng đoạn con

Remember to use this editorial only when stuck, and not to copy-paste code from it. Please be respectful to the problem author and editorialist.
Submitting an official solution before solving the problem yourself is a bannable offence.

Author: Yunan

Nguồn: CSES

Gọi $s(i)$ ~s(i)~ là tổng tiền tố (prefix sum): $s(i)=a_1+a_2+...+a_i$ ~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$ ~i~ và có tổng bằng $x$ ~x~, ta cần tìm tất cả các giá trị $j < i$ ~j < i~ sao cho:

$\displaystyle s(i)-s(j)=x$ $$\displaystyle s(i)-s(j)=x$$

, điều này tương đương với:

$\displaystyle s(j)=s(i)-x$ $$\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$ ~i~, chỉ cần kiểm tra xem giá trị $s(i) - x$ ~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))$ ~O(n.log(n))~

Editorial for Tổng đoạn con

Comments