구간 합 알고리즘

구간 합 알고리즘

연속적으로 나열된 수가 있을 때, 맨 앞부터 특정 위치까지의 합을 미리 구해 놓고 사용하는 알고리즘

 

• 시간 복잡도

- O(1)

 

 

구간 합 핵심 이론

[ 예시 ]

• 합 배열 S를 만드는 공식

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

- A[0]부터 A[i]까지의 합

 

• 구간 합을 구하는 공식

S[j] - S[i - 1]

- i에서 j까지 구간 합

 

 

 

 

 

* <Do It! 알고리즘 코딩테스트 with C++편>, <이것이 취업을 위한 코딩 테스트다 with 파이썬>을 참고하였습니다.