Problem
实现一个数据结构来有效地计算连续数组元素的总和。
输入
第一行包含一个自然数N (1 ≤ N ≤ 100000) —数组中数字的数量。
第二行包含从 1 到 100000 的 N 个数字——数组元素。
第三行包含一个自然数K(1 ≤ K ≤ 30000)—请求数量计算金额。
接下来的 K 行包含两个数字——数组段左右元素的编号（假设数组的元素从1开始编号）。'
印记
对于每个查询，打印数组相应部分的数字总和。在一行中打印数字，以空格分隔。
<正文>
| 输入 |
输出 |
5
4 4 8 7 8
2
1 2
1 3
| 8 16 |