구간 합 질문

문제

정수 $N$개 $A[1], A[2], \ldots, A[N]$과 질문 $Q$개가 주어진다. 질문마다 두 수 $l$, $r$이 주어지면 $A[l]$부터 $A[r]$까지의 합을 출력한다.

질문마다 $A[l]$부터 $A[r]$까지 더하면 너무 느리다. 누적합 $S[i] = A[1] + A[2] + \cdots + A[i]$를 먼저 구해 두면 질문 하나를 로 답할 수 있다.

제한

• $1 \le N, Q \le 100\,000$
• $1 \le l \le r \le N$