[알고리즘] 구간 합

합 배열

기존 배열을 전처리한 배열로 합배열을 미리 구해 놓으면 기존 배열의 일정 범위의 합을 구하는 시간 복잡도가 O(1)로 감소

합배열 s의 정의

s[i] = a[0] + a[1] + ... + a[i]

a[i]~a[j]까지 배열 합을 합 배열 없이 구하는 경우 최악의 경우 시간 복잡도가 O(N)

합 배열을 사용하면 O(1)안에 답을 구할 수 있다.

 

합 배열을 만드는 공식

S[i] = S[i-1] + A[i]

 

구간 합

합 배열을 이용하여 시간 복잡도를 더 줄이기 위해 사용하는 특수한 목적의 알고리즘

구간 합 알고리즘을 활용하기 위해선 합 배열을 우선 구해야 한다.

 

구간 합을 구하는 공식

S[j] - S[i-1]

 

 

관련 문제 보기

백준 11659번 구간 합 구하기 4