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

합 배열 S 정의

• S[i] = A[0] + A[1] + A[2] + ... + A[i-1] + A[i] // A[0]부터 A[i]까지의 합
• 합 배열은 기존 배열을 전처리한 배열
• 기존 배열의 일정 범위의 합을 구하는 시간 복잡도가 O(N)에서 O(1)로 감소

합 배열 S를 만드는 공식

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

구간 합을 구하는 공식

• S[j] - S[i-1] // i에서 j까지 구간 합

[003] 구간 합 구하기 1

• https://www.acmicpc.net/problem/11659
• 100,000 * 100,000 = 10,000,000,000 (100초) → 시간 초과 → 구간 합 이용
• 받는 데이터가 많을때는 BufferedReader를 사용하는 것이 더 빠름

[004] 구간 합 구하기 2

• https://www.acmicpc.net/problem/11660