인덱스 0 1 2 3 4 5
배열A 15 13 10 7 3 12
합배열S 15 28 38 45 48 60

구간 합을 구하는 공식

i에서 j까지 구간 합을 구할 때
S[j] - S[i-1]
3에서 5까지 구간 합을 구할 때
S[5] - S[2]

예를 들어 인덱스 2~5의 합을 구할 때

• 전체 인덱스 0~5
  S[5] = A[0] + A[1] + A[2] + A[3] +A[4] +A[5]
• 인덱스 0~1
  S[1] = A[0] + A[1]
• 인덱스 2~5는 전체에서 인덱스 0~1을 빼면 된다
  S[5] - S[1] = A[2] + A[3] +A[4] +A[5]