🫂 Prefix Sum

intro

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

 

✊🏻 예를 들면, 5개의 데이터로 구성된 수열 {10, 20, 30, 40, 50}이 있다고 가정했을 때, 2번째 수부터 4번째 수까지의 합은 20 + 30 + 40인 90이 된다.

 

✊🏻 N개의 정수로 구성된 수열이 있고, M개의 query 정보가 주어진다. 각 query는 left와 right로 구성. 각 query에 대하여 [left, right] 구간에 포함된 데이터들의 합을 출력해야 한다. (수행 시간 제한은 O(N+M))

 

→ 위 예와 접목하자면, 5개의 데이터 (N=5)로 구성된 수열에서 매번 새로운 query 구간마다 해당 합을 구한다면 시간 복잡도는 O(N*M)

→ 이 때, 시간의 효율성을 위해 구간 합(Prefix Sum; Interval Sum) 아이디어를 사용!

 

※ 구간 합 = 배열의 맨 앞부터 특정 위치까지의 합을 미리 구해 놓은 것 ※

→ 따라서 N개의 수 위치 각각에 대하여 접두사 합을 계산하여 P에 저장한 뒤, 매 M개의 쿼리 정보를 확인할 때 구간 합은 P[Right] - P[Left-1]

 

* code>

#구간 합 구하기
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]) #70

 

 

 

 

---

이코테 2021