[알고리즘] 누적 합 배열(Prefix Sum Matrix)

이전 알고리즘 글 '누적 합'을 먼저 보고 오시는 걸 권장합니다.

---

누적 합 배열(Prefix Sum Matrix)

주어진 2차원 배열이 있을 때, 각 위치 (i,j)에 (1,1)부터 (i,j)까지의 직사각형 영역에 있는 모든 원소들의 합을 저장한 배열(행렬).

원본 배열을 A, 누적 합 배열을 Z라고 할 때, Z[i][j]는

이고,

이는 P[i][j]는 원본 행렬의 좌상단 모서리(1,1)부터 현재 위치(i,j)까지 형성되는 직사각형 영역 내의 모든 원소들의 합.

 

크기가 N * M인 2차원 배열의 누적 합 배열을 구하는 과정의 경우 시간 복잡도는 O(NM).

누적 합을 통해 배열의 특정 구간[L, R]의 합을 구할 때 시간 복잡도는 O(1).

→ Q번의 질의가 있는 경우, O(N)+O(Q)이므로 시간 복잡도는 O(NM+Q).

 

만약 누적 합을 사용하지 않는 경우, Q번의 질의가 있는 경우 전체 시간 복잡도는 O(NMQ).

---

과정

원본 배열 A가 아래의 표와 같다고 해보자.

2	0	0	5	1
1	0	3	0	0
0	8	5	0	2
4	1	0	0	6
0	9	2	7	0

Z[i][j] = Z[i-1][j] + Z[i][j-1] - Z[i-1][j-1] + A[i][j] 인데,

 

 

Z[i-1][j]는 현재 위치의 바로 위까지의 직사각형 영역 합.

Z[i][j-1]은 현재 위치의 바로 왼쪽까지의 직사각형 영역 합.

Z[i-1][j-1]은 두 영역이 중복되는 부분으로, 빼기.

A[i][j]는 현재 위치의 원본 값을 더하기.

 

인데, 배열에는 Z[N][0], A[0][M]요소가 없기 때문에 가상으로 만들어주겠다.

 

 

0	0	0	0	0	0
0	2	0	0	0	0
0	0	0	0	0	0
0	0	0	0	0	0
0	0	0	0	0	0
0	0	0	0	0	0

 

이러면

Z[1][1] = Z[0][1] + Z[1][0] - Z[0][0] + A[1][1]

= Z[1][1] = 0 + 0 - 0 + 2

= 2

이를 차례차례 진행하여 나타낸다.

 

Z[1][1]부터 Z[i][j]까지의 사각형의 총 합을 Z(i,j)라고 해보자.

A의 [A][B]부터 [C][D]까지의 사각형 범위의 정수의 총 합은

Z(C, D) + Z(A-1, B-1) - Z(A-1, D) - Z(C, B-1)로 나타낼 수 있다.

---

구현

 

#include <bits/stdc++.h>
using namespace std;

int main()
{
    int H, W, Q;
    cin >> H >> W;
    int matrix[H][W];
    int prefixSumMatrix[H + 1][W + 1];

    for (int i = 0; i < H; i++)
    {
        for (int j = 0; j < W; j++)
        {
            int X;
            cin >> X;
            matrix[i][j] = X;
        }
    }

    // prefixsummatrix 배열 초기화[0][0]
    for (int i = 0; i <= H; i++)
    {
        for (int j = 0; j <= W; j++)
        {
            prefixSumMatrix[i][j] = 0;
        }
    }

    // 2차원 누적합 계산
    for (int i = 1; i <= H; i++)
    {
        for (int j = 1; j <= W; j++)
        {
            prefixSumMatrix[i][j] = matrix[i - 1][j - 1] +
                                    prefixSumMatrix[i - 1][j] +
                                    prefixSumMatrix[i][j - 1] -
                                    prefixSumMatrix[i - 1][j - 1];
        }
    }

    // 누적합배열 출력
    for (int i = 0; i <= H; i++)
    {
        for (int j = 0; j <= W; j++)
        {
            cout << prefixSumMatrix[i][j] << " ";
        }
        cout << "\n";
    }

    cin >> Q;

    // Z[A][B]부터 Z[C][D]까지의 총합 질의.
    for (int i = 0; i < Q; i++)
    {
        int A, B, C, D;
        cin >> A >> B >> C >> D;
        cout << prefixSumMatrix[C][D] +
                    prefixSumMatrix[A - 1][B - 1] -
                    prefixSumMatrix[C][B - 1] -
                    prefixSumMatrix[A - 1][D]
             << "\n";
    }
    return 0;
}