Tổng Sản Lượng Điện Mặt Trời Trà Vinh

Mô tả

Nhà máy điện mặt trời Trà Vinh trải dài những cánh đồng tấm pin lấp lánh dưới nắng gay gắt miền Tây. Bộ phận vận hành ghi lại sản lượng phát điện theo từng ngày. Họ lưu dữ liệu vào một mảng số nguyên, trong đó mỗi phần tử là số kilowatt-giờ (kWh) sản xuất được trong ngày tương ứng. Mỗi tuần, ban quản lý cần tổng hợp sản lượng của nhiều khoảng ngày khác nhau để báo cáo, ví dụ như tổng lượng điện từ ngày thứ 3 đến ngày thứ 15. Nếu cứ mỗi lần truy vấn mà cộng lại từ đầu, công việc sẽ rất mất thời gian khi số lượng ngày và số lượng câu hỏi đều lớn. Nhiệm vụ của bạn là giúp bộ phận vận hành trả lời nhanh chóng $q$ truy vấn. Mỗi truy vấn yêu cầu tính tổng sản lượng điện từ ngày $l$ đến ngày $r$ (theo chỉ số mảng, đánh số từ 0).

Đầu vào

• Dòng đầu tiên chứa hai số nguyên $n$ và $q$ ($1 \le n, q \le 10^5$), lần lượt là số ngày và số truy vấn.
• Dòng thứ hai chứa $n$ số nguyên $a_0, a_1, \dots, a_{n-1}$ (), là sản lượng điện mỗi ngày.
• $q$ dòng tiếp theo, mỗi dòng chứa hai số nguyên $l$ và $r$ ($0 \le l \le r < n$), mô tả một truy vấn.

Đầu ra

• Với mỗi truy vấn, in ra một số nguyên trên một dòng riêng biệt là tổng sản lượng điện từ ngày $l$ đến ngày $r$.

Ràng buộc

• $1 \le n, q \le 10^5$.
• $0 \le a_i \le 10^6$.

Ví dụ

Đầu vào:

5 3 100 200 150 300 250 0 4 1 3 2 2

Đầu ra:

1000 650 150

Giải thích:

• Truy vấn 0 4: tổng của toàn bộ 5 ngày là $100 + 200 + 150 + 300 + 250 = 1000$.
• Truy vấn 1 3: tổng các ngày từ chỉ số 1 đến 3 là $200 + 150 + 300 = 650$.