구간합 배열(Prefix Sum)

 

 

구간한 배열이란? 

순차적 계산 모델에서 계산하기 위해 yi = yi - 1 + xi 공식을 사용하여,

각 출력 값을 순차적으로 계산하기 위해 사용되는 기법이다. (알고리즘이라기보단 테크닉이다)

 

---

그렇다 이해하기 힘들테니 쉽게 얘기 하겠다. 

어떠한 N크기의 배열이 있다 가정하자.

해당 배열에서 어떤 부분의 배열의 합을 구하려면 반복문을 통해 합을 구할 수 있다.O(N)

그러나 이러한 계산을 O(1)로 만들 수 있다면?!

구간합 배열을 사용하자 

 

1	2	3	4	5	6	...
1	3	6	10	15	21	...

 

N +1 크기의 배열을 만들어준다. 

이후 해당 인덱스들의 누적합을 N+1 크기의 배열에 채워나간다. 

 

만약  2~4 인덱스를 가진 요소들의  부분합을 구하고싶다면? 

(5인덱스에속한 N+1 배열의 값) - ( 2인덱스에 속한 N+1 배열의 값) 을 해주면 된다.  

 

---

 

11659번: 구간 합 구하기 4

import sys
input = sys.stdin.readline
n,m = map(int,input().split())

pfs = list(map(int,input().split()))
for i in range(n-1):
    pfs[i+1] += pfs[i]
pfs = [0] + pfs

for _ in range(m):
    a,b = map(int,input().split())
    print(pfs[b]-pfs[a-1])