구간합 구간 합은 합 배열을 이용해서 시간 복잡도를 줄이기 위해 사용하는 알고리즘 합 배열 S의 정의 A[0]부터 A[i]까지의 합 S[i] = A[0] + A[1] + A[2] + … + A[i-1] + A[i]; 합 배열은 기존의 배열을 전 처리한 배열로써 이런 식으로 미리 구해 놓으면 기존 배열의 일정 범위의 합을 구하는 시간 복잡도가 O(n) 에서 O(1)로 감소 인덱스 0 1 2 3 4 5 배열A 15 13 10 7 3 12 합배열 S 15 28 38 45 48 60 합 배열 S를 만드는 공식 S[i] = S[i-1] + A[i] 구간 합을 구하는 공식 S[j] - S[i-1] //i에서 j까지의 구간 합 구간 합을 예제 import java.util.Scanner; public class 구간..