접두사 합

 만약 [left index, right index]로 구성된 M개의 쿼리에 대해 구간합을 구하고자 한다면, 단순 반복으로는 시간복잡도가 O(NM)이 됩니다. 따라서 데이터의 개수가 1,000,000개인 경우에는 쿼리가 10개만 되어도 연산량이 급격하게 많아집니다.

 조금 더 효율적으로 구간합을 구할 수 있는 방법 중 하나가 바로 접두사 합(Prefix sum)입니다. 이 때, 접두사 합은 리스트의 맨 앞부터 특정 위치까지 누적 합을 구해 놓은 것을 의미합니다. 즉, 이후의 계산을 위해 일종의 캐싱을 해놓는 것이라 볼 수 있겠습니다. 접두사 합 알고리즘은 다음과 같이 진행됩니다.

---

1. N개의 수에 대하여 접두사 합(Prefix sum)을 계산하여 배열 P에 저장한다.

2. 매 M개의 쿼리 정보 [L, R]을 확인할 때, 구간 합은 P[R] - P[L - 1]이다.

---

 따라서 접두사 합 알고리즘을 이용하여 다음과 같이 손쉽게 구간합을 구할 수 있습니다. 아래 코드의 시간복잡도는 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 = 3
right = 4
print(prefix_sum[right] - prefix_sum[left - 1])