[자료구조/알고리즘] 2차원 누적 합 (2D Prefix Sum)
1. 2차원 누적 합
2차원 누적 합(2D Prefix Sum)은 기존 1차원 누적 합 을 2차원까지 확장시킨 개념으로 기존 1차원 누적 합이 1차원 배열의 구간 합을 효율적으로 구할 수 있었다면, 2차원 누적 합은 2차원 배열의 영역 합을 효율적으로 구할 수 있는 전처리 기법이다.
주어진 2차원 배열에서 반복적으로 임의의 사각형 영역의 합을 구해야 하는 문제를 상상해보자. 2차원 배열의 크기가 $N \times M$, 쿼리의 수가 $K$ 일 때, 각 쿼리마다 매번 주어진 영역의 시작 위치부터 끝 위치까지 더하는 과정을 반복한다면 $O(N \times M \times K)$ 의 시간복잡도와 $O(1)$ 의 공간복잡도가 소요될 것이다.
이때 2차원 누적 합을 활용하면 $O(N \times M)$ 의 공간복잡도를 소요하는 대신 $O(N \times M + K)$ 의 시간복잡도로 문제를 해결할 수 있다.
2차원 누적 합의 기본 아이디어는 $(1, 1), \ldots, (N, M)$ 까지 임의의 영역이 있을 때, $(r_i, c_i)$ 부터 $(r_j, c_j)$ 까지의 합은 $(1, 1)$ 부터 $(r_j, c_j)$ 까지의 합에서 $(1, 1)$ 부터 $(r_i - 1, c_j)$ 까지의 합과 $(1, 1)$ 부터 $(r_j, c_i - 1)$ 까지의 합을 빼주고 $(1, 1)$ 부터 $(r_i - 1, c_i - 1)$ 까지의 합을 더해준 것과 같다.
예를 들면 $5 \times 5$ 크기의 2차원 배열이 있다 했을 때 아래 파란 영역의 합을 구해야 한다.
주어진 2차원 배열의 각 영역을 좀 더 세분화하면 아래와 같이 네 가지 영역으로 구분할 수 있다.
이때 노란색 영역의 합을 $y$, 초록색 영역의 합을 $g$, 보라색 영역의 합을 $v$, 파란색 영역의 합을 $b$ 라고 하면 아래와 같이 파란색 영역의 합을 표현할 수 있다.
여기서 $(y + g + v + b)$ 는 아래와 같은 영역이고,
$(y + g)$ 는 아래와 같은 영역이고,
$(y + v)$ 는 아래와 같은 영역이고,
$(y)$ 는 아래와 같은 영역이다.
위 4가지 영역 모두 $(0, 0)$ 부터 임의의 영역 $(r, c)$ 까지의 합이라는 구조를 띄고 있는데, 2차원 누적 합 배열은 $(r, c)$ 에 $(0, 0)$ 부터 $(r, c)$ 까지의 영역의 합을 전처리로 가지고 있어서 임의의 영역의 합을 구하는 각 쿼리를 $O(1)$ 의 시간복잡도로 해결한다.
2차원 누적 합 역시 1차원 누적 합처럼 원본 테이블이 정적 테이블일 때 효율적이다.
2. 2차원 누적 합 예시
주어진 2차원 배열($arr$)이 아래와 같을 때 다음과 같이 2차원 누적 합 배열($prefix\ sum$)을 생성할 수 있다.
이때 2차원 누적 합 배열의 행, 열 인덱스 $0$ 은 패딩으로 두면 1차원 누적 합 때처럼 깔끔하게 작성할 수 있다. $(0, 0)$ 부터 $(r, c)$ 까지의 합은 $(0, 0)$ 부터 $(r - 1, c)$ 까지의 합에서 $(0, 0)$ 부터 $(r, c - 1)$ 까지의 합을 더하고 $(0, 0)$ 부터 $(r - 1, c - 1)$ 까지의 합을 뺀 후 $(r, c)$ 의 값을 더하면 구할 수 있다. 각각의 값들이 전부 $O(1)$ 의 시간복잡도로 조회할 수 있기 때문에 $O(N \times M)$ 의 시간복잡도로 2차원 누적 합 배열을 생성할 수 있다.
$(2, 2)$ 부터 $(4, 3)$ 의 영역 합은 2차원 누적 합 배열에서 $91 - 29 - 42 + 14$ 로 구할 수 있다.
$(1, 1)$ 부터 $(3, 4)$ 의 영역 합은 2차원 누적 합 배열에서 $94 - 15 - 16 + 1$ 로 구할 수 있다.
3. 2차원 누적 합 코드
행, 열 인덱스 $0$ 에 패딩을 준 덕분에 2차원 누적 합을 초기화할 때 음수 인덱스를 참조하게 되는 예외 처리를 하지 않아도 되게 된다.
1. 2차원 누적 합 [Java]
1
2
3
4
5
6
7
8
9
10
// 초기화
int[][] pSum = new int[1 + N][1 + N];
for (int i = 1; i <= N; i++) {
for (int j = 1; j <= N; j++) {
pSum[i][j] = pSum[i - 1][j] + pSum[i][j - 1] - pSum[i - 1][j - 1] + map[i - 1][j - 1];
}
}
// 쿼리 (x1, y1) ~ (x2, y2)
pSum[x2][y2] - pSum[x1 - 1][y2] - pSum[x2][y1 - 1] + pSum[x1 - 1][y1 - 1];
2. 2차원 누적 합 [C++]
1
2
3
4
5
6
7
8
9
10
// 초기화
vector<vector<int>> psum(1 + n, vector<int>(1 + n));
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= n; j++) {
psum[i][j] = psum[i - 1][j] + psum[i][j - 1] - psum[i - 1][j - 1] + map[i - 1][j - 1];
}
}
// 쿼리 (x1, y1) ~ (x2, y2)
psum[x2][y2] - psum[x1 - 1][y2] - psum[x2][y1 - 1] + psum[x1 - 1][y1 - 1];