https://www.youtube.com/watch?v=O514yiWg8YE&list=PLFgS-xIWwNVX-zm4m6suWC9d7Ua9z7fuT&index=11

📌 구간 합

◾ 구간 합이란?

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

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

→ 합 배열은 배열을 전처리한 배열과 같다.
합 배열을 미리 구해놓으면 시간 복잡도가 O(N) 에서 O(1)로 감소

◾ 합 배열을 만드는 공식

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

◾ 합 배열을 빠르게 만드는 법

• A배열에서 i에서 j까지의 구간합을 구하는 경우,
  S[j] - S[i-1]
  
  ex) A 배열에서 2~5번째 구간 합을 구하고 싶은 경우
  S[5] - S[1]
  S[5] = A[0] ~ A[5]의 합
  S[1] = A[0] ~ A[1]의 합