Tổng Đoạn Tín Hiệu Sinh Hiệu Chợ Rẫy

Mô tả

Tại phòng phân tích tín hiệu sinh học của Bệnh viện Chợ Rẫy, kỹ sư viên thu thập một đoạn ghi điện tâm đồ dưới dạng mảng số nguyên biểu diễn biên độ sóng theo từng mili giây. Trong quá trình đọc kết quả, bác sĩ yêu cầu xem tổng biên độ trên nhiều khoảng thời gian liên tục khác nhau để phát hiện sớm các đoạn bất thường. Vì số truy vấn rất lớn, bạn cần giúp kỹ sư viên viết một công cụ trả lời mỗi truy vấn gần như ngay lập tức.

Nhiệm vụ của bạn là: cho mảng tín hiệu độ dài $n$ và $q$ truy vấn, mỗi truy vấn gồm hai chỉ số $l$ và $r$ $(0 \le l \le r < n)$, hãy tính tổng các phần tử từ chỉ số $l$ đến chỉ số $r$ của mảng tín hiệu.

Đầu vào

• Dòng đầu chứa số nguyên $n$ — số lượng mẫu tín hiệu.
• Dòng thứ hai chứa $n$ số nguyên $a_0, a_1, \dots, a_{n-1}$ — biên độ tín hiệu tại mỗi mili giây, cách nhau bởi khoảng trắng.

Đầu ra

• Với mỗi truy vấn, in ra một dòng chứa tổng các phần tử trong đoạn $[l, r]$.

Ràng buộc

• $1 \le n \le 10^5$
• $1 \le q \le 10^5$

Ví dụ

Đầu vào:

6 5 -3 8 2 -1 4 3 0 2 1 4 3 5

Đầu ra:

10 6 5

Giải thích:

• Truy vấn 0 2: tính tổng $a_0 + a_1 + a_2 = 5 + (-3) + 8 = 10$.