Hướng dẫn giải của Bài 2: Cắt lát mảng tiền tố (SUBMAX.CPP)

Chỉ dùng lời giải này khi không có ý tưởng, và đừng copy-paste code từ lời giải này. Hãy tôn trọng người ra đề và người viết lời giải.
Nộp một lời giải chính thức trước khi tự giải là một hành động có thể bị ban.

1. Tóm tắt đề bài

Cho dãy ~A~ gồm ~N~ số nguyên và ~Q~ truy vấn. Mỗi truy vấn gồm 2 số ~L, R~ (~1 \le L \le R \le N~). Với mỗi truy vấn, tính tổng các phần tử trong đoạn từ chỉ số ~L~ đến ~R~:

~ S(L, R) = \sum_{i=L}^{R} A_i ~

  • Dữ liệu vào (Input):

    • Dòng 1: Hai số nguyên ~N, Q~ (~1 \le N, Q \le 10^5~).
    • Dòng 2: ~N~ số nguyên ~A_1, A_2, \dots, A_N~ (~-10^9 \le A_i \le 10^9~).
    • ~Q~ dòng tiếp theo, mỗi dòng gồm 2 số nguyên ~L, R~.

  • Dữ liệu ra (Output):

    • Gồm ~Q~ dòng, mỗi dòng in ra tổng các phần tử trong đoạn ~[L, R]~.

2. Phân tích bài toán & Giới hạn

  • Giới hạn kích thước: ~N, Q \le 10^5~.

    • Nếu dùng vòng lặp duyệt tính tổng từng đoạn cho mỗi truy vấn (thuật toán trâu ~\mathcal{O}(N \times Q)~), số phép tính tối đa có thể lên tới ~10^5 \times 10^5 = 10^{10}~ thao tác, chắc chắn bị quá thời gian (Time Limit Exceeded - TLE).
    • Do đó, bài toán đòi hỏi phải tiền xử lý dữ liệu để trả lời mỗi truy vấn trong thời gian ~\mathcal{O}(1)~. Kỹ thuật tối ưu và trực quan nhất là Mảng cộng dồn (Mảng tiền tố - Prefix Sum).

  • Lưu ý tràn số:

    • Giá trị mỗi phần tử lên tới ~|A_i| \le 10^9~, tổng tối đa của dãy ~N = 10^5~ phần tử có thể đạt khoảng ~10^{14}~, vượt xa giới hạn kiểu số nguyên 32-bit (int). Bắt buộc phải dùng kiểu nguyên 64-bit (long long trong C++) cho mảng tiền tố.

3. Thuật toán xử lý

  • Kỹ thuật Mảng cộng dồn (Prefix Sum):

    1. Khởi tạo mảng pref kích thước ~N + 1~ với pref[0] = 0.
    2. Xây dựng mảng cộng dồn với quy tắc: ~pref[i] = pref[i - 1] + A_i \quad (1 \le i \le N)~ Trong đó pref[i] là tổng các phần tử từ vị trí ~1~ đến ~i~.
    3. Với mỗi truy vấn ~[L, R]~, tổng các phần tử từ vị trí ~L~ đến ~R~ được tính trực tiếp trong ~\mathcal{O}(1)~ bằng công thức: ~S(L, R) = pref[R] - pref[L - 1]~

  • Độ phức tạp:

    • Thời gian:
      • Tiền xử lý tính mảng cộng dồn: ~\mathcal{O}(N)~.
      • Trả lời mỗi truy vấn: ~\mathcal{O}(1)~.
      • Tổng thời gian: ~\mathcal{O}(N + Q)~ — với ~N, Q \le 10^5~, thuật toán chạy trong khoảng ~0.05 - 0.1~ giây.
    • Không gian (bộ nhớ): ~\mathcal{O}(N)~ để lưu mảng tiền tố (khoảng ~800\text{ KB}~, hoàn toàn tối ưu).
Đang tải...