구간 합

문제

성호는 정수 $N$개가 적힌 수열 $A_1, A_2, \ldots, A_N$을 가지고 있다. 질의 $Q$개가 주어지고, 질의마다 두 수 $l$, $r$이 있다. 질의마다 $A_l + A_{l+1} + \cdots + A_r$을 출력한다.

질의마다 $l$번부터 $r$번까지 하나씩 더하면 최대 $N \times Q$번 더해야 하므로 시간 안에 끝나지 않는다. 누적합 $S_i = A_1 + \cdots + A_i$를 미리 구해 두면 질의 하나를 한 번으로 계산한다.

제한

• $1 \le N, Q \le 100\,000$
• $-10^9 \le A_i \le 10^9$