연속적으로 나열된 n개의 수가 있을 때 특정 구간의 모든 수를 합한 값을 계산하는 문제

• N개의 정수로 구성된 수열이 있다
• M개의 쿼리 정보가 주어진다
• 각 쿼리는 Left와 Right으로 구성된다
• 각 쿼리에 대해서 [Left, Right] 구간에 포함된 데이터들의 합을 출력해라
• 수행제한시간은 O(n+m)

n = 5
data = [10,20,30,40,50]

sum_value = 0
prefix_sum = [0]
for i in data:
    sum_value+=i
    prefix_sum.append(sum_value)

left = 2
right = 4
print(prefix_sum[right] - prefix_sum[left-1])

N개의 숫자를 더하는 연산을 M번 하면 O(NM) = O(N2)시간이 걸림

접두사 합(prefix sum)을 활용: 맨 앞부터 특정 위치까지의 합을 미리 구한 배열

Left에서 Right까지의 합은 P[Right] - P[Left-1]

구간합 계산 = O(n)

M개 쿼리 연산 O(M)

O(N+M)