구간의 합

★ 합 배열을 이용하여 시간 복잡도를 더 줄이기 위해 사용하는 알고리즘이다.

 

• 먼저 합 배열 S 는 S[i] = A[0] + A[1] + A[2] + ... + A[ i - 1 ] + A[ i ] 로 정의된다.
• 합 배열은 전처리한 배열이라고 생각하면 된다.
• 합 배열을 미리 구해 놓으면 기존 배열의 일정 범위의 합을 구하는 시간복잡도가 O(N)에서 O(1)로 감소하게 된다.

 

• O(1)이 가능하게 해주는 합 배열 공식은 S[ i ] = S[ i - 1] + A[ i ] 이다.
• i 에서 j 까지 구간의 합을 구하는 공식은 S[ j ] - S[ i - 1] 이다
• A[2]에서 A[5]까지의 합을 구한다고 하면
  • S[5] = A[0] + A[1] + A[2] + A[3] + A[4] + A[5]
  • S[1] = A[0] + A[1]
  • S[5] - S[1] = A[2] + A[3]+ A[4] + A[5]
• 합 배열만 미리 구해두면 구간의 합은 한번의 계산으로 구할 수 있기 때문에 합 배열과 구간 합 공식을 적재적소에 활용하면 시간 복잡도를 줄이는데 많은 도움을 준다!

 

출처: Do it! 코딩테스트 c++