Algorithms/Prefix Sums

2.14.2 2D Prefix Sum

개념

직사각형 영역의 합을 여러 번 구할 때 사용합니다. Pi,jP_{i,j}는 첫 행·첫 열부터 (i,j)(i,j)까지의 합입니다. 바깥쪽 00번 행과 열은 00으로 둡니다.

누적 합 구성

위쪽 영역과 왼쪽 영역을 더하면 왼쪽 위 영역이 두 번 들어갑니다. 이를 한 번 빼고 현재 값을 더합니다.

Pi,j=Pi−1,j+Pi,j−1−Pi−1,j−1+Ai,j.P_{i,j}=P_{i-1,j}+P_{i,j-1}-P_{i-1,j-1}+A_{i,j}.

직사각형 영역의 합 구하기

행 x1x_1부터 x2x_2, 열 y1y_1부터 y2y_2까지의 합은 다음과 같습니다.

Px2,y2−Px1−1,y2−Px2,y1−1+Px1−1,y1−1.P_{x_2,y_2}-P_{x_1-1,y_2}-P_{x_2,y_1-1}+P_{x_1-1,y_1-1}.

첫 항은 원하는 직사각형을 포함하는 큰 영역입니다. 여기서 x1x_1보다 위에 있는 행과 y1y_1보다 왼쪽에 있는 열을 각각 뺍니다. 그러면 왼쪽 위의 겹친 영역은 두 번 빠지므로 마지막 항으로 한 번 더합니다.

예를 들어 격자의 첫 행이 [1,2,3][1,2,3], 둘째 행이 [4,5,6][4,5,6]일 때, 둘째 행의 둘째 열부터 셋째 열까지 합은 5+6=115+6=11입니다. 누적 합으로는 전체 2121에서 첫 행의 합 66과 첫 열의 합 55를 빼고, 두 번 뺀 왼쪽 위 값 11을 더해 21−6−5+1=1121-6-5+1=11을 얻습니다.

격자의 값이 고정되어 있고 서로 다른 직사각형의 합을 여러 번 구할 때 사용합니다. 직사각형의 넓이와 관계없이 네 개의 누적 합으로 답을 구합니다.

복잡도

격자의 행·열 수를 R,CR,C라고 합니다.

연산시간복잡도공간복잡도
2차원 누적합 전처리O(RC)O(RC)누적합 O(RC)O(RC)
직사각형 합 질의O(1)O(1)추가 O(1)O(1)

예제

문제

격자에서 주어진 직사각형 영역의 합을 구하여라.

입력

첫째 줄에 행 수 RR, 열 수 CC, 질의 수 QQ가 공백을 사이에 두고 주어진다. 1≤R,C≤301\le R,C\le30; 1≤Q≤1001\le Q\le100이다.

다음 RR개 줄에 각 행의 원소 CC개가 공백을 사이에 두고 주어진다. 각 원소는 11 이상 100100 이하의 정수이다.

다음 QQ개 줄에 영역의 왼쪽 위 좌표와 오른쪽 아래 좌표 x1,y1,x2,y2x_1,y_1,x_2,y_2가 공백을 사이에 두고 주어진다. 1≤x1≤x2≤R1\le x_1\le x_2\le R; 1≤y1≤y2≤C1\le y_1\le y_2\le C이다. xx는 행 번호, yy는 열 번호이며 두 경계를 모두 포함한다.

출력

각 영역의 합을 한 줄에 출력한다.

예제 입력

2 3 2
1 2 3
4 5 6
1 2 2 3
2 1 2 1

예제 출력

16
4

예제 코드

C++20

#include <iostream>

using namespace std;

int p[31][31];

int main() {
    int n, m, q, i, j, x, a, b, c, d;

    cin >> n >> m >> q;
    for (i = 1; i <= n; ++i) {
        for (j = 1; j <= m; ++j) {
            cin >> x;
            // 위쪽 합과 왼쪽 합에서 두 번 포함된 왼쪽 위 영역을 한 번 뺌
            p[i][j] = p[i - 1][j] + p[i][j - 1] - p[i - 1][j - 1] + x;
        }
    }
    for (i = 0; i < q; ++i) {
        cin >> a >> b >> c >> d;
        // 큰 직사각형에서 위·왼쪽 영역을 빼고 두 번 빠진 공통 영역을 더함
        cout << p[c][d] - p[a - 1][d] - p[c][b - 1] + p[a - 1][b - 1] << '\n';
    }
}