알고리즘 구간 합

구간 합

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

 

합 배열

배열에서 특정 범위에 존재하는 요소의 합

 

합 배열 정의

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

ex) i가 4일 때 합 배열  = A [ 0 ] ~ A [ 4 ] 까지의 합

쉽게말해 누적합을 말한다.

 

합 배열 공식

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

 

구간합 공식 

배열 인덱스 i 부터 인덱스 j 까지의 합

S [ j ] - S [ i - 1 ]

ex) 2 ~ 5까지의 합 = S [ 5 ] - S [ 1 ]

 

• 배열 A 의 0 ~ 1까지의 합은 3 + 9 = 12 이다.
• 배열 A 의 2 ~ 5까지의 합은 5 + 10 + 4 + 8 = 27이다.
• 합 배열 S [ 5 ] = 36 이다.
• 합 배열 S [ 1 ] = 9 이다.
• 합 배열 S [ 5 ]인  36에서 합배열 S [ 1 ]인 9를 빼면 27 이 된다.

다시한번 식으로 표현하자면 아래와 같다

S [ 5 ] = A [ 0 ] + A [ 1 ] + A [ 2 ] + A [ 3 ] + A [ 4 ] + A [ 5 ]

   ⊝ (MINUS)

S [ 1 ] = A [ 0 ] + A [ 1 ] 

   = A [ 2 ] + A [ 3 ] + A [ 4 ] + A [ 5 ]

 

결과적으로 주어진 구간합 공식에 정의된 합 배열간의 차를 통해 2 ~ 5까지의 합인 27과 동일한 결과값이 나오게 된다. 

 

 

 

번외

Q. 합배열 문제에서 배열의 값이 자주 바뀐다면?

Segment(Index) Tree