구간 합

🤔 구간 합이란?

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

📌 합 배열을 이용한 구간 합 구하기

• 예시)
  리스트 A = [15, 13, 10, 7, 3, 12]
  합 배열 S = [15, 28, 38, 45, 48, 60]
• 합 배열을 구하는 공식 : S[i] = S[i] + A[i]
•  구간 합 구하기 : S[j] - S[i-1]
• 리스트 A[2]부터 A[5] 까지 구간 합을 구하는 문제에서 합 배열을 통해 구하면,
  S[5] - S[1]로 계산할 수 있다. 시간 복잡도 O(1) 이 된다.
• 합 배열을 사용하지 않고, 리스트로 구간 합을 구한다면,
  A[0] + ... + A[5] - (A[0]+A[1]) 로 구할 수 있고, 시간 복잡도는 리스트 길이만큼 탐색해야하기 때문에,
  시간 복잡도 O(1) 이 된다.
• 결론은 합 배열을 활용하여 구간 합을 구하면, 시간 복잡도를 줄이는 데 많은 도움이 된다.