Tổng Chi Phí Vận Tải Container Cảng Cẩm Phả

Mô tả

Cảng Cẩm Phả là một trong những điểm trung chuyển container nhộn nhịp nhất miền Bắc. Dọc theo bến cảng có N bãi container xếp liền nhau theo một đường thẳng, đánh số từ 1 đến N. Bãi thứ i có chi phí vận tải (tính bằng nghìn đồng) là a[i].

Hàng ngày, bộ phận kế toán nhận được rất nhiều yêu cầu kiểm tra chi phí vận tải của một dãy bãi liên tiếp từ bãi l đến bãi r (gồm cả hai đầu). Vì số lượng yêu cầu rất lớn, việc cộng dồn tay từng phần tử mỗi lần sẽ quá chậm. Nhiệm vụ của bạn là viết một chương trình sử dụng kỹ thuật tiền tố tổng (prefix sum) để tính trước một mảng cộng dồn, từ đó trả lời tức thì cho Q truy vấn.

Đầu vào

• Dòng đầu tiên chứa hai số nguyên n và q (1 ≤ n ≤ 10^5, 1 ≤ q ≤ 10^5).
• Dòng thứ hai chứa n số nguyên a[1], a[2], ..., a[n] — chi phí vận tải từng bãi (0 ≤ a[i] ≤ 1000).
• q dòng tiếp theo, mỗi dòng chứa hai số nguyên l và r (1 ≤ l ≤ r ≤ n) mô tả một truy vấn.

Đầu ra

• In ra q dòng, mỗi dòng là một số nguyên duy nhất: tổng chi phí vận tải từ bãi l đến bãi r.

Ràng buộc

• 1 ≤ n ≤ 10^5
• 1 ≤ q ≤ 10^5
• 0 ≤ a[i] ≤ 1000
• 1 ≤ l ≤ r ≤ n
• Tổng chi phí tối đa của một truy vấn không vượt quá 10^8.

Ví dụ

Đầu vào:

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

Đầu ra:

8 11 1

Giải thích:

• Truy vấn 1: tổng bãi 1 đến 3 = 3 + 1 + 4 = 8.
• Truy vấn 2: tổng bãi 2 đến 5 = 1 + 4 + 1 + 5 = 11.
• Truy vấn 3: chỉ lấy bãi 4, kết quả là 1.