Bach Lieu Coder - Bài tập

MTK50 - Truy vấn tổng - QSUM

Dữ liệu vào: Standard input

Dữ liệu ra: Standard output

Giới hạn thời gian: 1.0 giây

Giới hạn bộ nhớ: 128 megabyte

Đăng bởi: phanhieubl

Cho một dãy số nguyên gồm N phần tử nguyên A₁, A₂, …, A_N.

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 ≤ 10⁵)
Dòng thứ 2 chứa N số nguyên A₁, A₂, …, A_N (|A_i| ≤ 10³)
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

QSUM.INP

QSUM.OUT

Giải thích ví dụ

5 3

1 3 -4 5 -2

1 4

2 5

3 3

-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.

Bài tập mới

Coder tích cực