Problem
Triển khai cấu trúc dữ liệu để tính tổng các phần tử mảng liên tiếp một cách hiệu quả.
Đầu vào
Dòng đầu tiên chứa 1 số tự nhiên N (1 ≤ N ≤ 100000) — số lượng các số trong mảng.
Dòng thứ hai chứa N số từ 1 đến 100000 — phần tử mảng.
Dòng thứ ba chứa một số tự nhiên K (1 ≤ K ≤ 30000) — số lượng yêu cầu để tính số tiền.
K dòng tiếp theo chứa hai số — số của các phần tử bên trái và bên phải của đoạn mảng (giả sử rằng các phần tử của mảng được đánh số từ một).'
Dấu ấn
Đối với mỗi truy vấn, in tổng các số của phần tương ứng của mảng. In các số trên một dòng cách nhau một dấu cách.
| Đầu vào |
Đầu ra |
5
4 4 8 7 8
2
1 2
1 3
| 8 16 |