Tiền tố tổngMảng
Mô tả
Mùa cao điểm, nhà ga quốc nội Sân bay Tân Sơn Nhất tấp nập không ngớt. Ban quản lý ghi lại số lượng khách có mặt tại nhà ga theo từng khung giờ liên tiếp trong ngày, bắt đầu từ khung giờ thứ 0. Một ngày được chia thành đúng n khung giờ.
Đội vận hành cần trả lời rất nhiều truy vấn để phân bổ nhân sự an ninh và hướng dẫn viên. Mỗi truy vấn yêu cầu tính tổng số khách tích lũy từ khung giờ L đến khung giờ R (bao gồm cả hai đầu). Vì số lượng truy vấn khá lớn, bạn cần tìm cách trả lời mỗi truy vấn trong thời gian rất nhanh.
Đầu vào
- Dòng đầu tiên chứa số nguyên n (1 ≤ n ≤ 10^5) — số lượng khung giờ trong ngày.
- Dòng thứ hai chứa n số nguyên a[0], a[1], ..., a[n-1] (0 ≤ a[i] ≤ 1000), mỗi số cách nhau bởi một khoảng trắng — số khách tại mỗi khung giờ.
- Dòng thứ ba chứa số nguyên q (1 ≤ q ≤ 10^5) — số lượng truy vấn.
- q dòng tiếp theo, mỗi dòng chứa hai số nguyên L và R (0 ≤ L ≤ R ≤ n-1) — khoảng khung giờ cần tra cứu.
Đầu ra
- Với mỗi truy vấn, in ra một dòng chứa tổng số khách từ khung giờ L đến khung giờ R.
Ràng buộc
- 1 ≤ n ≤ 10^5
- 0 ≤ a[i] ≤ 1000
- 1 ≤ q ≤ 10^5
- 0 ≤ L ≤ R ≤ n-1
- Tổng khách trong bất kỳ khoảng nào không vượt quá 10^8.
Ví dụ
Đầu vào:
5 120 80 200 150 90 3 0 2 1 3 0 4
Đầu ra:
400 430 640
Giải thích từng bước:
- Truy vấn 0 đến 2: 120 + 80 + 200 = 400 khách.
- Truy vấn 1 đến 3: 80 + 200 + 150 = 430 khách.
- Truy vấn 0 đến 4: 120 + 80 + 200 + 150 + 90 = 640 khách — tổng cả ngày.