도입

부분 합이란 배열의 각 위치에 대해 배열의 시작부터 현재 위치까지의 원소의 합을 구해 둔 배열입니다. 이 배열을 사용해 특정 구간의 합을 $O(1)$에 구할 수 있습니다. 부분 합을 사용하지 않으면 $O(n)$에 구할 수 밖에 없습니다.

부분 합 계산하기

구간 합을 빠르게 계산하기 위해서는 부분 합을 미리 계산해 둘 필요가 있습니다. 부분 합을 계산하는데 드는 시간은 수열의 길이에 따라 선형으로 증가한다는 점에 유의합시다. 반복문을 통해 구간 합을 구하기 위해 최대 $O(N)$의 시간이 걸린다는 점을 돌이켜 보면, 구간 합을 두 번 이상 구할 때는 대부분의 경우 부분 합을 사용하는 쪽이 이득입니다.

// 주어진 배열 a의 부분 합을 계산한다.
static int[] partialSum(final int[] a) {
    int[] result = new int[a.length];
    result[0] = a[0];
    for (int i = 1; i < a.length; i++) 
        result[i] = result[i - 1] + a[i];
    return result;
}
// 어떤 배열의 부분합 psum[]이 주어질 때, 원래 배열의 a부터 b까지의 합을 구한다.
static int rangeSum(final int[] psum, int a, int b) {
    if (a == 0) return psum[b];
    return psum[b] - psum[a - 1];
}

2차원으로의 확장

2차원 배열 $A[][]$이 주어질 때, $A[y_1,x_1]$에서 $A[y_2,x_2]$까지의 직사각형 구간의 합을 계산해야 한다고 합시다. 다음과 같은 부분 합 배열을 사용해 이 구간 합을 빠르게 구할 수 있습니다.

$psum[y,x]=\sum_{i=0}^y\sum_{j=0}^x A[i,j]$

$psum[y,x]$는 $(0,0)$을 왼쪽 위 칸, $(y,x)$를 오른쪽 아래 칸으로 갖는 직사각형 구간에 포함된 원소들의 합입니다.
구간 합을 구하는 식은 다음과 같습니다.

$sum(y_1, x_1, y_2, x_2)=psum[y_2, x_2]-psum[y_2, x_1 - 1]-psum[y_1 - 1, x_2] + psum[y_1 - 1, x_1-1]$

아래 코드는 구간 합을 구하는 함수의 구현을 보여줍니다.

// 어떤 2차원 배열 A[][]의 부분합 psum[][]이 주어질 때,
// A[y1, x1]과 A[y2, x2]를 양 끝으로 갖는 부분 배열의 합을 반환한다.
static int gridSum(final int[][] psum, int y1, int x1, int y2, int x2) {
    int result = psum[y2][x2];
    if (y1 > 0) result -= psum[y1 - 1][x2];
    if (x1 > 0) result -= psum[y2][x1 - 1];
    if (y1 > 0 && x1 > 0) result += psum[y1 - 1][x1 - 1];
    return result;
}

예제: 합이 0에 가장 가까운 구간

양수와 음수가 모두 포함된 배열 $A[]$가 있을 때, 그 합이 0에 가장 가까운 구간을 찾는 문제를 풀어 봅시다. 이런 구간을 찾는 한 가지 방법은 $A$의 모든 구간을 순회하면서 각각의 합을 계산하는 것입니다. 이렇게 하면 배열의 길이 $N$에 대해 $O(N^2)$의 시간이 걸립니다.
하지만 부분 합을 사용하면 이 문제를 아주 쉽게 풀 수 있습니다. 구간 합을 사용하면 $A[i]$ ~ $A[j]$ 구간의 합은 다음과 같이 표현할 수 있습니다.

$\sum_{k=i}^j A[k]=psum[j]-psum[i-1]$

이 값이 0에 가깝다는 말은 $psum[]$의 두 값의 차이가 가장 적다는 뜻입니다. 주어진 배열에서 가장 가까운 두 값을 찾기 위한 간단한 방법은 이 배열을 정렬한 뒤 인접한 원소들을 확인하는 것입니다. 정렬은 $O(N\log N)$시간에 수행할 수 있고, 부분 합을 구하는 것과 인접한 원소들을 확인하는 것 모두 $O(N)$에 할 수 있으니 이 알고리즘의 수행 시간은 $O(N\log N)$이 됩니다.

참고문헌: 구종만, 프로그래밍 대회에서 배우는 알고리즘 문제해결전략, 인사이트, (2012)