구간 합

시간 복잡도 단축을 위한 구간 합 배열 S를 생성

합 배열 S

배열 A {15, 13, 10, 7, 3, 12}
합 배열 S {15 28, 38, 45, 48, 60}

합 배열 공식

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

합 배열을 구해두면 구간 합을 한번의 계산으로 구할 수 있다.

S[j] - S[i-1] //i에서 j까지 구간 합
S[5] - S[1] = A[2] + A[3] + A[4] + A[5]

2차원 배열에서의 구간 합

1행과 1열의 구간 합은 다음과 같다.

D[i][1] = D[i-1][1] + A[i][1] //행
D[1][j] = D[1][j-1] + A[1][j] //열

이를 통해 (3,3) 등의 공식을 구해본다.

D[3][3] = D[2][3] + D[3][2]- D[2][2] + A[3][3]
위 아래의 구간합을 더해준 뒤 중복으로 더해진 D[1][1] 을 빼고 현재 값을 더함

일반식

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