76. Prefix Sum

누적합(Prefix Sum)은 원소의 값이 변하지 않을 때 임의의 연속된 구간에 속한 원소들의 합을 빠르게 구하기 위해 사용되는 방법이다. 아이디어와 구현 모두 간단하며 다양하게 응용할 수 있다. 일반적으로 $1$차원 누적합이 많이 사용되지만 $2$차원 누적합이 사용되는 경우도 존재한다. $3$차원 이상의 누적합은 잘 사용되지 않는다.

 

길이가 $n$인 $1$차원 배열 $a$가 존재할 때 누적합 $s_i$는 일반적으로 다음과 같이 정의된다.

$$s_0 = 0$$

$$s_i = a_i+s_{i-1}\ (1 \le i \le n)$$

즉 $s_i$는 첫 번째 원소부터 $i$번째 원소까지의 합과 같다. $s_i$를 구했다면 임의의 연속된 구간에 속한 원소들의 합은 다음과 같이 구할 수 있다.

$$\sum_{k=l}^r a_k = s_r-s_{l-1}\ (1 \le l \le r \le n)$$

누적합을 사용하지 않을 경우 합을 구하기 위해 일일히 원소들을 더해야 하지만 누적합을 사용할 경우 항상 두 개의 값만 확인하면 구간 합을 구할 수 있다.

 

$2$차원 누적합은 다음과 같이 정의하고 사용할 수 있다. 크기가 $n \times m$인 $2$차원 배열 $a$가 존재할 때 누적합 $s_{i, j}$는 다음과 같다.

$$s_{i, j} = \begin{cases}0 & (i=0 \text{ or } j=0) \\ a_{i, j}+s_{i-1, j}+s_{i, j-1}-s_{i-1, j-1} & (1 \le i \le n \text{ and } 1 \le j \le m)\end{cases}$$

이렇게 정의하면 $s_{i, j} = \sum_{x=1}^i \sum_{y=1}^j a_{x, y}$가 된다. 이 상태에서 임의의 직사각형 구간에 포함된 원소들의 합을 다음과 같이 구할 수 있다.

$$\sum_{x=lx}^{rx} \sum_{y=ly}^{ry} a_{x, y} = s_{rx, ry}-s_{lx-1, ry}-s_{rx, ly-1}+s_{lx-1, ly-1}$$

이번에는 네 개의 값을 확인해야 하지만 범위 내의 값들을 하나씩 더하는 것보다 훨씬 빠르다는 사실은 변하지 않는다.

 

[연습문제]

 

BOJ 11659. 구간 합 구하기 4 (Silver III)

$1$차원 누적합으로 쿼리를 처리하는 기본적인 문제이다.

 

BOJ 11660. 구간 합 구하기 5 (Silver I)

$2$차원 누적합으로 쿼리를 처리하는 기본적인 문제이다.

 

BOJ 2143. 두 배열의 합 (Gold III)

누적합을 이용하여 배열 $A$의 구간합과 $B$의 구간합을 전부 구한 다음 $A$의 구간합과 $B$의 구간합을 더해서 $T$가 되는 경우의 수를 세면 된다. 개수를 세는 것은 정렬 후 투 포인터로 할 수도 있고 이분 탐색으로 할 수도 있다. map을 써도 제한시간 내에 돌아간다고 한다.

 

BOJ 2571. 색종이 - 3 (Gold III)

색종이가 붙은 칸을 $1$, 아닌 칸을 $0$으로 놓으면 $0$이 하나도 없는 가장 큰 직사각형 구간을 찾는 문제가 된다. 이것은 가능한 왼쪽 위와 오른쪽 아래 꼭짓점 조합을 모두 확인하는 $\Theta(n^4)$ 완전탐색으로 구할 수 있다.

 

BOJ 19566. 수열의 구간 평균 (Gold II)

수열의 모든 값에서 $K$를 빼면 구간합이 $0$인 구간의 수를 세는 문제가 된다. 이것은 누적합이 서로 같은 쌍의 개수를 세는 것과 같다. 쌍의 개수는 누적합을 전부 map에 넣어서 구할 수 있다.

 

→ solved.ac tag: prefix_sum