연속적으로 나열된 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])
Python
복사
N개의 숫자를 더하는 연산을 M번 하면 O(NM) = O(N2)시간이 걸림
접두사 합(prefix sum)을 활용: 맨 앞부터 특정 위치까지의 합을 미리 구한 배열
Left에서 Right까지의 합은 P[Right] - P[Left-1]
구간합 계산 = O(n)
M개 쿼리 연산 O(M)
O(N+M)
