📘[Data Structure] 구간 합

구간 합?

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

합 배열을 먼저 구해야하는 것이 중요하다.

리스트 A가 있을 때, 합 배열 S는 아래와 같이 정의할 수 있다.

# A[0] ~ A[i] 까지의 합

S[i] = A[0] + A[1] + A[2] + ... + A[i-1] + A[i]

이처럼 합 배열은 기존의 리스트 데이터를 전처리한 배열이라고 생각하면 된다!

이렇게 합 배열을 먼저 구해 놓으면 기존 리스트의 일정 범위의 합을 구하는 시간 복잡도가 O(N)에서 O(1)로 줄어든다.

합 배열과 구간 합을 구하는 공식이 있다?

합 배열을 구하는 공식은 다음과 같다!

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

이렇게 구현하면 합 배열을 이용해 구간 합 또한 쉽게 구할 수 있다.

i에서 j까지의 구간 합을 구하는 공식은 다음과 같다!

S[j] - S[i-1]

관련 문제

백준[11659] - 구간 합 구하기 4