구간 합
합 배열을 이용해 시간 복잡도를 더 줄이기 위해 사용하는 특수한 목적의 알고리즘이다.
핵심이론 (1차원)
구간 합 알고리즘을 활용하려면, 먼저 합 배열을 구해야한다.
배열 A가 있을 때 합 배열 S는 다음과 같이 정의한다.
합 배열 S 정의
S[i] = A[0] + A[1] + A[2] + ... + A[i-1] + A[i] // A[0]부터 A[i]까지의 합
합 배열을 기존 배열을 전처리한 배열이라 생각하면 된다.
합 배열을 미리 구해놓으면, 기존 배열의 일정 범위의 합을 구하는 시간 복잡도가 O(N)에서 O(1)로 감소한다.
-> A[i] ~ A[j]까지의 배열 합을 합 배열 없이 구하는 경우, 최악의 경우는 i==0 , j ==N인 경우로 시간 복잡도는 O(N)이다.
합 배열 S를 만드는 공식
S[i] = S[i-1] + A[i]
이렇게 구현된 합 배열을 이용해 구간 합 역시 쉽게 구할 수 있다.
구간 합을 구하는 공식
S[j] - S[i-1] //i~j 구간 합
합 배열만 미리 구해두면, 구간 합은 한 번의 계산으로 구할 수 있는것이다!
시간 복잡도를 줄이는데, 많은 도움이 될 것이다.
기본적인 1차원 구간 합 배열외에도, 2차원 구간 합 배열이있다.
2차원 구간 합 배열
구간 합 배열 1행, 1열은 다음과 같이 구해진다.
D[i][1] = D[i-1][1] + A[i][1]
D[1][i] = D[1][i-1] + A[1][i]
이를 통해 나머지 2차원 구간 합 배열을 채운다.
D[i][j]의 값을 채우는 구간 합 공식
D[i][j] = D[i][j-1] + D[i-1][j] - D[i-1][j-1] + A[i][j]
즉 그림으로 보면, (0,0) ~X 까지의 구간합을 구하기위해서,c + b를 하고 공통으로 두 번 더해진 a를 한 번 빼고, 해당 자리의 원본 값인 X를 더한다.
-> (0,0) ~X 까지의 구간합 = c + b - a + X
질의 X1,Y1,X2,Y2에 대한 답을 구간 합으로 구하는 방법
D[X2][Y2] - D[X1-1][Y2] - D[X2][Y1-1] + D[X1-1][Y1-1]
예를들어, (3,3) ~ (4,4)의 구간합을 구한다면(진한 파랑 부분), (4,4)의 값에서 하늘색 부분과 노란색 부분을 빼고, 중복해서 빠진 주황색 부분을 한 번 더한다.
