구간 합은 시간복잡도를 줄이기위해 누적 합 배열을 이용한 알고리즘입니다.

1. 누적 합 배열 정의

배열A가 있을때 합배열S는 다음과 같이 정의 됩니다.

//A[0]부터 A[i]까지의 합
S[i] = A[0] + A[1] + A[2] + ... + A[i-1] + A[i]

이렇게 합 배열을 미리 구해놓으면 기존배열의 구간합을 구하는 시간복잡도가 O(N)에서 O(1)로 감소합니다.

2. 누적 합 배열 만드는 공식

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

//인덱스 0말고 1부터 시작하는걸로 베이스 삼는다.
int sum = 0;
for(int i = 1; i <=N; i++){
	sum += A[i];
	S[i] = sum;
}

//인덱스 0말고 1부터 시작하는걸로 베이스 삼는다.
int[] S = new int[1+N];
for(int i = 1; i <=N; i++){
	S[i] = S[i-1] + A[i];
}

3. 구간 합을 구하는 공식

// i 부터 j까지의 구간 합
S[j] - A[i-1]

다음 공식을 예시로 설명해보겠습니다.

// A[2]에서 A[5]까지의 구간합을 구한다.
S[5] = A[0] + A[1] + A[2] + A[3] + A[4] + A[5] 
S[1] = A[0] + A[1]
S[5] - S[1] = A[2] + A[3] + A[4] + A[5]