누적합 알고리즘(prefix sum)

이 알고리즘은 "값의 변경이 없을때" 빠르게 구간합을 구하기 위한 알고리즘으로 시간 복잡도는 O(N) 입니다.

일단 배열 a를 받아 줍니다.

 

예시)

a = [0] + list(map(int,input().split())) #zero index사용 x

 

그 후, 1부터 a의 길이 번 반복하여 전에있는 값을 더해 줍니다.

 

예시)

a = [0] + list(map(int,input().split())) #zero index 사용 x
for i in range(1,len(a)):   #index error을 방지 하기 위하여 1부터 시작
	a[i] += a[i-1] # 자신에다가 뒤에 닜는 값을 더함

 

이때 a가 [1,2,3,4,5]라고 가정하면, 다음과 같이 변경 됩니다.

[1,3,6,10,15]

 

이제 이걸로 구간합을 구하면 끝입니다.

구간 합을 구하는 방법은 간단합니다.

만약에 a가 [1,2,3,4,5]고 2부터 4까지 합을 구해야 한다면

4는 변경된 a값에서 1부터 4의 값을 모두 가지고 있으므로

a[4]에다가 a[1]을 빼주면 됩니다.

 

예시)

a = [0]+list(map(int,input().split())) #zero index 사용 x
for i in range(1,len(a)):   #index error을 방지 하기 위하여 1부터 시작
	a[i] += a[i-1] # 자신에다가 뒤에 닜는 값을 더함
n,k = map(int,input().split()) # 어디서부터 어디까지 합을 구할 것 인가?
print(a[k]-a[n-1]) #k까지의 구간에다가 n전의 구간을 더함.

 

지금까지 prefix sum 포스팅 이였습니다.

감사합니다.