연속적으로 나열된 N개의 수가 있을때, 특정 구간 내 모든 수를 더하는 알고리즘에 대해 파악한다.
다만, 단순히 1차원 리스트에서 선형탐색을 하며 합산하는 것이 아닌, 여러 정보와 구간이 제시될때 시간복잡도를 최소화하는 방안을 고민할 필요가 있다.
매 Query마다 선형탐색을 하지 않고도 구간 합을 구하는데 시간복잡도를 최소화할 수 있는 방안 중 하나로, 접두사합 알고리즘(prefix sum)을 활용한다.
미리 각각의 숫자까지의 합(접두사 합)을 계산하여 미리 저장해 놓고, M개의 Query를 확인할 때마다 저장한 값을 그대로 활용하여 구간합을 구한다.
#접두사 합을 통한 구간 합 구하는 알고리즘 도출하기
n = 5
data = [10, 20, 30, 40, 50]
#sum result
sum = 0
#prefix sum, index = 0은 0으로 초기화, 노드1부터 계산하는 것임.
prefixSum = [0]
for i in data:
sum = sum + i
prefixSum.append(sum)
#구간합 계산
left = 3
right = 4
print(prefixSum[right]-prefixSum[left-1])
2021 이코테 - 접두사합 알고리즘
https://www.youtube.com/watch?v=cswJ1h-How0&list=PLRx0vPvlEmdAghTr5mXQxGpHjWqSz0dgC&index=9