Editorial for Tổng mảng 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

Subtask 1: Ta đơn giản duyệt qua các chỉ số $(i,j)$ ~(i,j)~ và kiểm tra tổng tương ứng.

Độ phức tạp: $O(N^3)$ ~O(N^3)~

Subtask 2: Để tính toán nhanh tổng của mảng con từ $i$ ~i~ đến $j$ ~j~, ta có thể sử dụng Tổng tiền số $($ ~(~Prefix Sum $)$ ~)~ để tính toán trong $O(1)$ ~O(1)~.

Độ phức tạp: $O(N^2)$ ~O(N^2)~

Subtask 3: Gọi $count_s$ ~count_s~ là số lượng chỉ số $i$ ~i~ thỏa mãn $prefix\_sum_i=s$ ~prefix\_sum_i=s~. Với mỗi vị trí $i$ ~i~, ta cần đếm số lượng chỉ số $j$ ~j~ $(j \ge i)$ ~(j \ge i)~ thỏa mãn $prefix\_sum_j=prefix\_sum_{i-1}$ ~prefix\_sum_j=prefix\_sum_{i-1}~, hay nói cách khác chính là $count_{prefix\_sum_{i-1}}$ ~count_{prefix\_sum_{i-1}}~.

Độ phức tạp: $O(N.\log(N))$ ~O(N.\log(N))~

Editorial for Tổng mảng con

Comments