구간 합 계산

구간 합 문제는 연속적으로 나열된 N개의 수가 있을 때, 특정 구간의 모든 수를 합한 값을 구하는 문제이다. 예를 들어 (N = 5인) 수열 {10, 20, 30, 40, 50} 이 있다고 해보자. 여기서 두번째 수부터 네번째 수 까지의 합은 20 + 30 + 40 = 90이 될것이다. 이때 다수의 구간에 대해서 합을 각각 구하도록 M번 요구 된다면, 모든 요구에 따라 구간합을 구한다면 최악의 경우 O(NM) 시간 복잡도를 가진다. 이때 접두사 합을 이용해서 구간 합 계산을 빠르게 수행할 수 있다. 접두사 합이란 리스트의 맨 앞부터 특정 위치까지의 합을 구해놓은 것을 의미한다.

1. N개의 수에 대하여 접두사 합을 계산하여 배열 p에 저장한다.
2. 매 M개의 쿼리 정보 [L, R] 을 확인할 때, 구간 합은 P[R] - P[L - 1] 이다.

• 결과적으로 매 쿼리 마다 P[R] - P[L - 1] 을 계산하면 되기 때문에, 전체 구간합을 모두 계산하는 작업은 O(N + M) 의 시간 복잡도를 가진다.

소스코드

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

# 접두사 합(prefix_sum) 배열 계산
sum_value = 0
prefix_sum = [0]
for i in data:
    sum_value += i
    prefix_sum.append(sum_value)

#구간 합 계산(3번째 수 부터 4번째 수 까지)
left = 3
right = 4
print(prefix_sum[right] - prefix_sum[left - 1]) #70