구간 합

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

구간 합 알고리즘을 활용하려면 합 배열을 구해야 한다.

합 배열을 미리 구해 놓으면 기존 배열의 일정 범위의 합을 구하는 시간 복잡도가 O(N)에서 O(1)로 감소한다.

 

1차원 배열의 합 배열

1차원 합 배열 S 정의

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

 

합 배열 S를 만드는 공식

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

 

i-1에서 알 수 있듯 합 배열은 기존 배열보다 하나 크게 생성해서 1번 인덱스부터 값이 들어간다.

 

i에서 j까지의 합을 구하는 공식

S [j] - S [i-1]

 

1에서 3까지의 구간합 S [3] - S [0]

5에서 5까지의 구간합 S [5] - S [4]

 

 

2차원 배열의 합 배열

참고하면 이해하기 쉽다.

https://www.youtube.com/watch?v=KT864Aa3zE0

 

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

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

 

2차원 합 배열 D를 만드는 공식

D [X][Y] = D [X][Y-1] + D [X-1][Y] - D [X-1][Y-1] + A [X][Y]

구하려는 위치 =  좌측 + 위 - 좌측 위 + 원본 배열의 수

 

(X1, Y1)에서 (X1, Y2)까지의 합을 구하는 공식

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

구하려는 공간의 합 = 구하려는 공간까지의 전체 합 - 윗 공간의 합 - 좌측 공간의 합 + 윗 공간과 좌측 공간의 교집합