📖 Bài giảng & lời giải: đây là Bài tập 7 trong bài giảng Chuyên đề nhập môn 7: File và nhập xuất nhanh trên blog Lập trình thuật toán – có lý thuyết, mô phỏng từng bước, gợi ý và code C++ / Python.

⚠️ Lưu ý: hãy đảm bảo em đã thật sự cố gắng tự làm bài trước, rồi mới xem gợi ý và lời giải nhé!

🎓 Khóa học Lập trình Thuật toán thi đấu của thầy Nguyễn Việt Nam Sơn – 111 buổi video, kèm cặp cá nhân, luyện thi chuyên Tin · HSG Tin học · Tin học trẻ · đội tuyển quốc gia · Olympic/ICPC. 👉 Xem chi tiết khóa học · Thành tích học viên

📞 Đăng ký học: Zalo 0767 666 702 · Facebook Nguyễn Việt Nam Sơn · 🌐 laptrinhthuattoan.blogspot.com

📂 Lưu ý về đọc/ghi file: trên blog, bài này dùng để luyện đọc dữ liệu từ file và ghi kết quả ra file (kiểu BAI1.INP / BAI1.OUT như trong kỳ thi HSG). Trên ClueOJ, chương trình của em phải đọc dữ liệu từ bàn phím (stdin) và in kết quả ra màn hình (stdout), không cần mở file nào. Em có thể dùng mẹo trong bài giảng: chỉ gọi freopen khi mở được file, ví dụ if(fopen("BAI1.INP", "r")){ freopen("BAI1.INP", "r", stdin); freopen("BAI1.OUT", "w", stdout); }, để cùng một bài nộp chạy được cả ở phòng thi lẫn trên ClueOJ.

Cho dãy $n$ số nguyên $a_1, a_2, \ldots, a_n$ và $q$ truy vấn, mỗi truy vấn gồm hai số $l$, $r$. Với mỗi truy vấn, hãy tính tổng $a_l + a_{l+1} + \ldots + a_r$.

Dữ liệu rất lớn và giới hạn thời gian chặt, em cần dùng nhập xuất nhanh (C++: ios::sync_with_stdio(false); cin.tie(nullptr); và in '\n' thay cho endl; Python: sys.stdin.buffer.read().split() và gom kết quả để in một lần).

Dữ liệu vào

• Dòng 1: hai số nguyên $n$, $q$ ($1 \le n, q \le 5 \cdot 10^5$).
• Dòng 2: $n$ số nguyên $a_i$ ($|a_i| \le 10^9$).
• $q$ dòng tiếp theo, mỗi dòng gồm hai số nguyên $l$, $r$ ($1 \le l \le r \le n$).

Kết quả

In ra $q$ dòng, dòng thứ $i$ là tổng của đoạn ứng với truy vấn thứ $i$.

Sample Input

5 3
1 -2 3 4 5
1 5
2 3
4 4

Sample Output

11
1
4