Cho một dãy số nguyên gồm N phần tử nguyên A1, A2, …, AN.
Yêu cầu: Hãy trả lời Q truy vấn có dạng:
- i j: tính tổng các phần tử liên tiếp thuộc đoạn từ i đến j.
INPUT: QSUM.INP
Ø Dòng đầu tiên chứa 2 số nguyên dương N và Q (1 ≤ N, Q ≤ 105)
Ø Dòng thứ 2 chứa N số nguyên A1, A2, …, AN (|Ai| ≤ 103)
Ø Q dòng tiếp theo mỗi dòng chứa hai số nguyên i, j (1 ≤ i ≤ j ≤ N) thể hiện một câu hỏi truy vấn.
OUTPUT: QSUM.OUT
Ø Chứa Q dòng, mỗi dòng là câu trả lời truy vấn tương ứng trong INPUT.
Ví dụ:
QSUM.INP | QSUM.OUT | Giải thích ví dụ |
5 3 1 3 -4 5 -2 1 4 2 5 3 3 | 5 2 -4 | Dãy có 5 phần tử và 3 truy vấn - Truy vấn 1: tính tổng các phần từ thứ 1 đến thứ 4 là: 1 + 3 + (-4) + 5 = 5 - Tương tự như vậy ta được kết quả của 2 truy vấn còn lại là 2 và -4 |
* Ghi chú:
- Có 80% số test với dữ liệu cho là: 1 ≤ N, Q ≤ 5000.