[개념] 구간 합 (Prefix Sum)

# 구간 합

• 구간 합 : i ~ j 인덱스 값들의 합 => 특정 구간 인덱스의 합
• 부분 합 : 0 ~ k 인덱스 값들의 합 => 처음부터 특정 인덱스까지의 합
• 시간 복잡도
  • 반복문을 통해 i ~ j 인덱스 값들의 합을 구하는 경우) O(N) (i=0, j=N)
  • 시간 복잡도를 줄이기 위해서는 합 배열을 이용해야 함 => O(1)으로 감소

 

#  합 배열

합 배열 S, 배열 A
S[i] = A[0] + A[1] + A[2] + ... + A[i-1] + A[i]

• 합 배열 : 기존의 배열을 전처리한 배열합 배열 만드는 공식

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

• 합 배열을 이용해 구간 합 구하는 공식

S[j] - S[i-1]

---

# 관련 문제

[JAVA] 백준 q11659 - 구간 합 구하기 4

 

---

# 참고 글

• Do it 알고리즘 코딩테스트 자바편