Tổng Sản Lượng Gạo Cảng Cần Thơ

Mô tả

Cảng Cần Thơ là một trong những đầu mối xuất khẩu gạo lớn nhất vùng Đồng bằng sông Cửu Long. Mỗi ngày, cảng ghi lại sản lượng gạo xuất khẩu (tính bằng tấn) lên một bảng tổng sắp. Anh trưởng ca muốn nhanh chóng trả lời các câu hỏi của chủ tàu: "Từ ngày thứ $L$ đến ngày thứ $R$, cảng đã xuất tổng cộng bao nhiêu tấn gạo?"

Vì số ngày rất nhiều và lượng truy vấn khá lớn, bạn cần viết chương trình trả lời mỗi truy vấn trong thời gian cực nhanh, thay vì đếm lại từ đầu mỗi lần.

Đầu vào

• Dòng đầu chứa số nguyên $n$ — số ngày có trong bảng ghi chép ($1 \le n \le 10^5$).
• Dòng thứ hai chứa $n$ số nguyên $a_1, a_2, \ldots, a_n$ — sản lượng gạo xuất khẩu mỗi ngày, mỗi số cách nhau bởi một khoảng trắng ().
• Dòng thứ ba chứa số nguyên $q$ — số lượng truy vấn ($1 \le q \le 10^5$).
• $q$ dòng tiếp theo, mỗi dòng chứa hai số nguyên $L$ và $R$ mô tả khoảng ngày cần tính tổng ($1 \le L \le R \le n$).

Đầu ra

• Với mỗi truy vấn, in ra một dòng chứa tổng sản lượng gạo từ ngày $L$ đến ngày $R$.

Ràng buộc

• $1 \le n \le 10^5$
• $0 \le a_i \le 10^4$

Ví dụ

Đầu vào:

6 12 8 15 5 20 10 3 1 3 2 5 4 6

Đầu ra:

35 48 35

Giải thích từng bước: Sản lượng 6 ngày lần lượt là: 12, 8, 15, 5, 20, 10 tấn.

• Truy vấn $L=1, R=3$: $12 + 8 + 15 = 35$ tấn.
• Truy vấn $L=2,R=5$: tấn.

Nếu tính trước mảng tổng tiền tố $P$ với $P[0]=0$ và $P[i]=P[i-1]+a_i$, ta có . Mỗi truy vấn chỉ cần tính , ví dụ truy vấn 2: .