구간 합

구간 합

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

- 코딩 테스트에서 사용 빈도가 높으니 알아두기 !!

 

 

 

구간 합의 핵심 이론

// 배열 A가 있을 때 합 배열 S는 아래와 같이 정의함
S[i] = A[0] + A[1] + A[2] + ... + A[i-1] + A[i] // A[0]부터 A[i]까지의 합

• 합 배열은 기존의 배열을 전처리한 배열이라 생각하면 됨
• 합 배열을 미리 구해놓으면 기존 배열의 일정 범위의 합을 구하는 시간 복잡도가 O(N)에서 O(1)로 감소함

 

 

합 배열 S를 만드는 공식

// 합 배열 S를 만드는 공식
S[i] = S[i-1] + A[i]

 

 

구간 합을 구하는 공식

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

 

 

 

2차원 구간 합 배열 D[X][Y] 정의

D[X][Y] = 원본 배열의 (0, 0)부터 (X, Y)까지의 사각형 영역 안에 있는 수의 합

 

 

 

D[i][j]의 값을 채우는 구간 합 공식

D[i][j] = D[i][j-1] + D[i-1][j] - D[i-1][j-1] + A[i][j]

 

 

 

질의 X1, Y1, X2, Y2에 대한 답을 구간 합으로 구하는 방법

D[X2][Y2] - D[X1-1][Y2] - D[X2][Y1-1] + D[X1-1][Y1-1]