구간 합 (누적합)

제한

• $1 \le N, Q \le 10^5$
• $-10^4 \le A_i \le 10^4$
• $0 \le l \le r \le N-1$
• 답이 64비트 정수 범위를 벗어나지 않음

입출력 예시

입력 1

8 3
3 1 4 1 5 9 2 6
3 5
0 7
2 2

출력 1

15
31
4

설명: 첫 번째 질의는 위 그림의 예와 같이 $1+5+9=15$. 두 번째 질의는 전체 합으로 $3+1+4+1+5+9+2+6=31$. 세 번째 질의는 한 칸만의 합 .

입력 2

5 4
-2 3 -1 5 4
0 4
0 0
1 3
2 4

출력 2

9
-2
7
8

풀이 힌트

이 문제는 누적합 없이 풀면 한 질의에 최악 $O(N)$이 들어 전체 $O(NQ)$이다. $N = Q = 10^5$이면 이라 시간 안에 못 푼다. 누적합을 전처리하면 전체 이다.