Cho mảng gồm n số nguyên và q truy vấn. Mỗi truy vấn gồm hai số l và r (1≤l≤r≤n); hãy tính tổng các phần tử từ vị trí l đến vị trí r (bao gồm hai đầu). Hãy dùng kỹ thuật mảng cộng dồn (prefix sum) để trả lời nhanh.
Dòng đầu chứa hai số nguyên n và q.
Dòng thứ hai chứa n số nguyên cách nhau bởi dấu cách.
Tiếp theo là q dòng, mỗi dòng chứa hai số nguyên l và r.
1≤n,q≤105, −109≤ai≤109, 1≤l≤r≤n
Với mỗi truy vấn, in ra trên một dòng riêng một số nguyên là tổng của đoạn [l,r].
Ví dụ:
Đầu vào:
5 3
1 2 3 4 5
1 5
2 3
4 4
Đầu ra:
15
5
4
Giải thích:
Đang tải editor...