Tổng đoạn con bằng cộng dồn tiền tố
Một mảng nhỏ nhưng bị hỏi tổng liên tục trên nhiều đoạn khác nhau. Nếu mỗi câu hỏi lại chạy
Tiến độ của tôi ở bài này
Điểm và code bạn nộp được lưu vào tài khoản sau khi chấm bài.
Đang tải điểm của bạn…
Kiến thức và chủ đề
Kiến thức tiên quyết: cpp-basics, arrays.
Nội dung đề bài
Mô tả bài toán
Một mảng nhỏ nhưng bị hỏi tổng liên tục trên nhiều đoạn khác nhau. Nếu mỗi câu hỏi lại chạy một vòng lặp cộng từ l đến r, chương trình vẫn chạy được nhưng lặp lại rất nhiều phép cộng. Mảng pref với pref[k] = a[1] + a[2] + ... + a[k] biến mỗi câu hỏi thành đúng một phép trừ.
Yêu cầu
Cho mảng a gồm n số nguyên đánh số từ 1 đến n. Với mỗi câu hỏi (l, r), hãy in tổng a[l] + a[l+1] + ... + a[r]. Cả hai đầu l và r đều được tính vào tổng.
Quy ước nộp bài
Nộp chương trình solution.cpp đọc dữ liệu từ stdin và in kết quả ra stdout. Mỗi câu hỏi in đúng một số nguyên trên một dòng riêng.
Input
- Dòng thứ nhất: số nguyên n là số phần tử (1 <= n <= 20).
- Dòng thứ hai: n số nguyên a[1] đến a[n], cách nhau bởi dấu cách (|a[i]| <= 10000).
- Dòng thứ ba: số nguyên q là số câu hỏi (1 <= q <= 10).
- q dòng tiếp theo: mỗi dòng hai số nguyên l rồi r, cách nhau bởi dấu cách
(1 <= l <= r <= n).
Output
- q dòng, dòng thứ i là tổng của đoạn trong câu hỏi thứ i.
Ràng buộc
- 1 <= n <= 20, 1 <= q <= 10, |a[i]| <= 10000.
- Tổng mọi đoạn con vừa với kiểu long long.
- Thời gian cho mỗi bộ dữ liệu là 1 giây.
Ví dụ 1
Input
5
1 2 3 4 5
2
1 3
2 5
Output
6
14
Ví dụ 2
Input
3
10 -5 7
3
1 1
2 3
1 3
Output
10
2
12
Giải thích
Với dữ liệu vào:
Câu hỏi 1 3 cho 1 + 2 + 3 = 6, câu hỏi 2 5 cho 2 + 3 + 4 + 5 = 14, nên kết quả là:
Gợi ý và lời giải chỉ mở sau khi bạn bấm Nộp bài. Giáo viên và quản trị viên mở được ngay.
Góp ý & báo lỗi bài tập
Đề bài chưa rõ, test có vấn đề hay bạn có ý tưởng giúp bài tốt hơn? Gửi cho đội ngũ AI Empire nhé — mỗi góp ý đều được đọc.
