Problem
連続する配列要素の合計を効率的に計算するデータ構造を実装します。
入力
最初の行には、1 つの自然数 N (1 ≤ N ≤ 100000) — が含まれています。配列内の数値の数。
2 行目には、1 から 100000 までの N 個の数字が含まれています。配列要素。
3 行目には、1 つの自然数 K (1 ≤ K ≤ 30000) — が含まれています。金額を計算するリクエストの数。
次の K 行には 2 つの数値が含まれています。配列セグメントの左右の要素の番号 (配列の要素は 1 から数えられると想定されます)'
インプリント
各クエリについて、配列の対応するセクションの数値の合計を出力します。数値をスペースで区切って 1 行に出力します。
<本体>
| 入力 |
出力 |
5
4 4 8 7 8
2
1 2
1 3
| 8 16 |