구간 합 구하기

정수가 들어 있는 배열, 예를 들어 1, 2, 3, 4, 5, 6, 7, 8, 9, 10이 있다고 하자. 모든 원소의 합은 반복문 하나로 쉽게 구한다.

int size = 10;
int total = 0;
for (int i = 0; i < size; i += 1) {
    total = total + v[i];
}

다른 구간의 원소만 더하고 싶다면 (예를 들어 5번 자리부터 7번 자리까지) 반복문의 몇 군데만 고치면 된다. 이 문제에서는 그 계산을 여러 번 해야 한다.

첫 줄에 배열의 크기 $n$이 주어진다. 둘째 줄에 배열의 원소 $n$개가 공백으로 구분되어 주어진다.

배열 다음 줄에는 질의의 개수 $m$이 주어진다. 이어지는 $m$개의 줄에는 질의가 한 줄에 하나씩 주어진다. 질의는 두 정수 start와 end로 이루어지며, start번 자리부터 end번 자리까지 원소의 합을 구해야 한다.

제한

• $1 \le n \le 100000$
• 배열의 자리는 0번부터 센다. start와 end는 배열에 있는 자리이고 0 <= start <= end <= n-1을 만족한다.
• 배열의 원소는 0 이상 9 이하의 정수이다.
• $1 \le m \le 10000$

질의마다 start번 자리부터 end번 자리까지 원소의 합을 한 줄에 하나씩 출력한다. 양 끝 자리도 합에 포함한다.

즉 array[start] + array[start+1] + ... + array[end-1] + array[end]를 출력한다.