[TEST!] Prefix Sum - Mảng tiền tố

Cho bài toán sau: Mảng ~a~ có ~n~ phần tử, phần tử ~a[i] = a_i~ là phần tử thứ ~i^\text{th}~. Có ~q~ truy vấn, mỗi truy vấn hỏi tổng giá trị các phần tử trong đoạn ~[l, r]~ là bao nhiêu.

Thuật toán "ngây thơ" (gà vcl hehehehehehehehe)

• Với mỗi truy vấn, ta lặp mảng từ ~l~ đến ~r~ để tính tổng giá trị.
  • Độ phức tạp thời gian: ~\mathcal{O}(q * n)~.

Thuật toán dùng Prefix Sum

• Xây dựng mảng Prefix Sum như sau:
  • ~p[0] = 0~;
  • ~p[i] = p[i - 1] + a[i] \; \forall \; i : 1 \le i \le n~.
• Vậy với mỗi truy vấn ~[l, r]~, ta chỉ việc lấy ~p[r] - p[l - 1]~ là ra kết quả.

Chứng minh tính đúng đắn

• Từ ~p[i] = a[1] + \dots + a[i]~, vậy nên:
  • ~p[l - 1] = a[1] + \dots + a[l - 1]~;
  • ~p[r] = a[1] + \dots + a[l - 1] + a[l] + \dots + a[r]~.
• Vậy ~p[r] - p[l - 1] = a[l] + \dots + a[r]~.

Tổng kết

• Chỉ có vậy thôi :v, các bạn có thể tìm hiểu thêm Prefix Sum cho mảng hai chiều, cập nhật phần tử dùng mảng hiệu (Difference Array).
• Bài tập kinh điển sử dụng Prefix Sum:
  • Tìm dãy con liên tiếp có tổng lớn nhất.

Bài toán: Tìm dãy con liên tiếp có tổng lớn nhất

• Ta có thể duyệt từng phần tử ~a[i]~ trong mảng và tính xem dãy con liên tiếp có tổng lớn nhất KẾT THÚC ở phần tử ~a[i]~ là bao nhiêu. Sau đó lấy max là ra kết quả.
• Giờ tính kiểu gì?
  • Nếu dãy con liên tiếp bắt đầu từ ~j~ kết thúc ở ~i~ thì tổng sẽ là ~p[i] - p[j - 1]~.
  • Để tổng lớn nhất thì hiển nhiên ~p[i] - p[j - 1]~ phải lớn nhất trong tất cả những giá trị ~j~ từ ~1~ đến ~i~.
    • Mà theo hướng giải ở trên, ta đã cố định được dãy con đó kết thúc tại ~i~ nên để tính xem dãy con liên tiếp có tổng lớn nhất là bao nhiêu thì chỉ cần tìm xem giá trị NHỎ NHẤT trong các ~p[j - 1]~ là bao nhiêu.
• Đến đây thì dễ rồi, các bạn tự giải tiếp nhé!