첫째 줄에 수의 개수 N과 합을 구해야 하는 횟수 M이 주어진다. 둘째 줄에는 N개의 수가 주어진다. 수는 1,000보다 작거나 같은 자연수이다. 셋째 줄부터 M개의 줄에는 합을 구해야 하는 구간 i와 j가 주어진다.
출력
총 M개의 줄에 입력으로 주어진 i번째 수부터 j번째 수까지 합을 출력한다.
제한
1 ≤ N ≤ 100,000
1 ≤ M ≤ 100,000
1 ≤ i ≤ j ≤ N
예제 입력 1
5 3
5 4 3 2 1
1 3
2 4
5 5
예제 출력 1
12
9
1
나의 풀이
완전 탐색으로 구간 합을 구할 경우 O(NM)이기 때문에 최악의 경우 100억 번의 연산이 필요
prefix sum으로 미리 구간 합을 구해서 해결
import sys
N, M = map(int, sys.stdin.readline().rstrip().split())
num_list = list(map(int, sys.stdin.readline().rstrip().split()))
prefix_sum = [0]
total = 0
for i in range(N):
total += num_list[i]
prefix_sum.append(total)
for _ in range(M):
start, end = map(int, sys.stdin.readline().rstrip().split())
print(prefix_sum[end] - prefix_sum[start - 1])