백준_11659_구간 합 구하기(누적합)

from sys import stdin
n, m = [int(v) for v in input().split()]
n_list = list(map(int, input().split()))

sum_list = [0] * (n+1)
for i in range(1, n+1):
    sum_list[i] = sum_list[i-1] + n_list[i-1]

for _ in range(m):
    s, e = [int(v) for v in stdin.readline().rstrip().split()]
    print(sum_list[e] - sum_list[s-1])

index로 매번 sum해서 풀게 되면 시간 복잡도가 O(n*m)이므로 주어진 시간안에는 풀 수 없는 문제다.

누적 합을 사용하면 쉽게 구할 수 있는 문제다