구간 합

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

합 배열 S

// A[0]부터 A[i]까지의 합
S[i] = A[0]+A[1]+A[2]+...+A[i-1]+A[i]

• 기존 배열을 전처리한 배열
• 미리 합배열을 구해두면 시간 복잡도가 O(N)에서 O(1)로 감소하게 된다.
• 적재적소에 잘 활용해보자.

// 합배열 S
S[i] = S[i-1]+A[i]

구간합

S[j]-S[i-1] // i에서 j까지 구간 합

관련 문제

• 구간 합 구하기 4
  • 런타임 관리가 조금 어려웠다.
• 구간 합 구하기 5
  • 배열로 확장하여 생각하느라 두 번 더하거나 빼지는 영역을 알아차리는 것이 힘들었다.
• 나머지 합 구하기
  • 자꾸 시간초과가 떠서 고민하던 와중에, '나머지 배열'이라는 아이디어를 얻었다.

참고

• Do it! 알고리즘