구간 합 구하기

면접 대비

시간 제한1초메모리 제한256 MB

요약

고정된 수열에 누적합을 미리 구해서 주어진 여러 구간의 합을 순서대로 출력합니다.

난이도: 쉬움10점 중 3점
유형: 누적 합, 배열
정답자: 아직 제출이 없습니다

문제

수 $N$ 개가 주어진다. 이 중 $i$ 번째 수부터 $j$ 번째 수까지 더한 값을 구하는 프로그램을 작성하시오.

입력

첫째 줄에 수의 개수 $N$ 과 합을 구해야 하는 횟수 $M$ 이 주어진다. 둘째 줄에 $N$ 개의 수가 순서대로 주어진다. 각 수는 1,000보다 작거나 같은 자연수이다. 셋째 줄부터 $M$ 개의 줄에 걸쳐 합을 구할 구간의 시작 위치 $i$ 와 끝 위치 $j$ 가 주어진다.

출력

$M$ 개의 줄에 걸쳐 각 구간의 합을 입력에 주어진 순서대로 한 줄에 하나씩 출력한다. $i$ 번째 수부터 $j$ 번째 수까지의 합은 양 끝을 모두 포함한다.

제한

$1 \le N \le 100{,}000$
$1 \le M \le 100{,}000$
$1 \le i \le j \le N$

예제2

예제 1
입력
```
5 3
5 4 3 2 1
1 3
2 4
5 5
```
예상 출력
```
12
9
1
```

예제 2

입력

12 6
1 2 3 4 5 6 7 8 9 10 11 12
1 12
6 6
1 6
7 12
2 11
12 12

예상 출력