# 구간 합 구간 합 : 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 11659번: 구간 합 ..
