Hướng dẫn cho Tổng dãy con
Chỉ sử dụng khi thực sự cần thiết như một cách tôn trọng tác giả và người viết hướng dẫn này.
Chép code từ bài hướng dẫn để nộp bài là hành vi có thể dẫn đến khóa tài khoản.
Chép code từ bài hướng dẫn để nộp bài là hành vi có thể dẫn đến khóa tài khoản.
Authors:
Ý tưởng bài này là sử dụng tổng tiền tố. Đặt \(s[i] = a[1] + a[2] + ... + a[i]\). Ta có thể tính mảng \(s\) trong một vòng for như sau:
s[0] = 0
for i = 1..n
s[i] = s[i - 1] + a[i]
Lưu ý tổng \(a[l] + ... + a[r] = (a[1] + a[2] + ... + a[r]) - (a[1] + a[2] + ... + a[l - 1]) = s[r] - s[l - 1]\).
Như vậy ta có thể tính mỗi truy vấn trong \(O(1)\).
Bình luận