Truy vấn tổng nhật ký tĩnh

Bối cảnh và bài toán

Một hệ thống lưu một chuỗi số liệu đã chốt và sẽ không còn thay đổi. Trong giai đoạn phân tích, có nhiều yêu cầu hỏi tổng số liệu trên một đoạn liên tiếp. Vì dữ liệu là tĩnh nhưng số truy vấn lớn, lặp lại phép cộng từ đầu cho mỗi yêu cầu sẽ gây lãng phí.

Yêu cầu

Trả lời tổng các phần tử trên mỗi đoạn [l,r] của mảng tĩnh.

Input

• Dòng 1: n q.
• Dòng 2: n số nguyên a[i].
• q dòng tiếp theo: mỗi dòng chứa l r.

Output

In tổng của từng đoạn theo thứ tự truy vấn.

Ràng buộc

• 1 <= n, q <= 2 * 10^5
• |a[i]| <= 10^9
• 1 <= l <= r <= n

Chấm điểm

Ví dụ 1

Input

5 3
3 2 4 5 1
2 4
1 5
3 3

Output

11
15
4

Giải thích. Các tổng tương ứng là 2+4+5=11, tổng toàn mảng 15, và phần tử thứ ba 4.

Ví dụ 2

Input

4 2
-5 10 -2 7
1 2
2 4

Output

5
15

Giải thích. Prefix sum vẫn hoạt động bình thường khi dữ liệu có số âm.

Thông tin bài tập

Nguồn: Phỏng theo CSES Problem Set — Static Range Sum Queries (Task 1646).

Tham khảo: https://cses.fi/problemset/task/1646/