구간 합 계산 (Prefix Sum)

구간 합 빠르게 계산하기

Prifix Sum이란 리스트의 앞에서부터 특정 위치까지의 합을 의미한다.

 

문제

N개의 정수로 구성된 수열이 있고, M개의 쿼리 정보가 주어진다.

각 쿼리는 L과 R로 구성된다. [L, R] 구간에 해당하는 데이터들의 합을 모두 구하는 문제이다.

시간제한은 O(N+M) 이다.

 

 

원리

1. Prefix Sum을 계산하여 임의의 배열 P에 저장한다.

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

 

10

20

30

40

50

Prefix Sum을 계산하면 아래와 같다.

0	10	30	60	100	150
P[0]	P[1]	P[2]	P[3]	P[4]	P[5]

 

 

코드

# 데이터 개수 n과 데이터 입력
n = 5
data = [10, 20, 30, 40, 50]

# Prefix Sum 계산
sum = 0
prefix_sum = [0] # 초기 값은 0이다. 
for i in data:
  sum += i
  prefix_sum.append(sum)

# 구간 합 계산
left = 3
right = 4
print(prefix_sum[right] - prefix_sum[left - 1])