<aside> 💡 부분합, 누적합이라 불리우는 배열의 일부 구간에 대한 합을 매우 빠르게 구할 수 있게 해주는 스킬이다. N개의 원소로 이루어진 배열이 주어졌을 떄 반복문을 통해 부분 배열의 합을 구하려면 O(N)이 걸리는데, 부분합을 이용하면 모든 부분합을 O(1)에 바로 구할 수 있다.

</aside>

1. 1차원 배열

arr을 순차 탐색하면서 sum 배열을 만들어주면 된다. aum[i] 에는 arr[0] + arr[1] + … arr[i-1]의 정보가 담겨있다.

활용법

arr의 i항부터 j항까지의 합을 S(i, j)라고 하자. 이 때 S(i, j) = sum[j+1] - sum[i] 이다.

2. 2차원 배열

2차원 배열도 같은 방식이다. arr을 순차 탐색하면서 sum 배열을 만들어주면 된다. 이 때, sum[i][j]에는 arr[0][0]부터 arr[i-1][j-1]까지의 합이 담겨있다고 생각하면 된다.

활용법

sum_arr[i][j] = arr[i-1][j-1] + sum_arr[i-1][j] + sum_arr[i][j-1] - sum_arr[i-1][j-1]

3. 2차원 구간합 활용법

이 sum_arr을 활용하면 2차원 배열에서도 상수 시간에 구간합을 구할 수 있게 된다.

arr의 (x1, y1)부터 (x2, y2)까지 합을 S라 할 때

S =  sum[x2+1][y2+1] - sum[x1][y2+1] - sum[x2+1][y1] + sum[x1][y1]