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 |