구간 합 (Interval Sum)

개념

• 연속적으로 나열된 N개의 수가 있을 때, 특정 구간의 모든 수를 합한 값을 계산하는 문제

문제 설명

• N개의 정수로 구성된 수열
• M개의 쿼리(Query) 정보가 주어짐
  • 각 쿼리는 Left, Right로 구성
  • 각 쿼리에 대해 [Left, Right]로 구간에 포함된 데이터들의 합을 출력
• 수행 시간 제한 : O(N + M)

문제 해결 아이디어

• 접두사 합 (Prefix Sum) 이용
  • 배열의 맨 앞부터 특정 위치까지의 합을 미리 구해 놓은 것

1. N개의 수 위치 각각에 대해 접두사 합을 계산해 배열 P에 저장
2. 매 M개의 쿼리 정보를 확인할 때, 구간 합은 P[Right] - P[Left - 1]

소스 코드 (Python)

n = #데이터의 개수
data = #배열

#접두사 합(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])

성능 분석

• 시간 복잡도 : $O(N)$