C++로 구현하는 2D 범위 합 쿼리 (변경 불가능 행렬)

2차원 행렬 matrix가 주어졌을 때, 왼쪽 위 모서리 좌표 (row1, col1)과 오른쪽 아래 모서리 좌표 (row2, col2)로 정의되는 직사각형 영역 내부에 있는 모든 요소의 합을 구하는 문제입니다.

예를 들어 행렬이 다음과 같다고 가정해 보겠습니다.

위 표에서 파란색으로 표시된 영역은 (2,1)과 (4,3)으로 정의된 직사각형이며, 이 영역의 합은 8입니다.

따라서 sumRegion(2, 1, 4, 3), sumRegion(1, 1, 2, 2), sumRegion(1, 2, 2, 4)와 같은 쿼리를 수행하면 각각 8, 11, 12를 반환해야 합니다.

접근 방법: 2D 누적합(Prefix Sum)

행렬이 변경되지 않고(immutable) 범위 합 쿼리가 여러 번 발생한다면, 매번 직사각형 내부를 순회하는 것은 비효율적입니다. 대신 2차원 누적합(DP) 테이블을 미리 계산해 두면 각 쿼리를 O(1) 시간에 처리할 수 있습니다.

알고리즘 단계

• 누적합을 저장할 행렬 dp를 정의합니다.
• n := 행의 개수. 만약 n이 0이면 즉시 반환합니다.
• m := 열의 개수
• dp := 크기가 n × m인 새로운 행렬을 생성합니다.
• i를 0부터 n-1까지, j를 0부터 m-1까지 반복하며 각 행별로 가로 방향 누적합을 계산합니다.
  • j - 1 < 0이면 dp[i][j] = matrix[i][j]
  • 그렇지 않으면 dp[i][j] = dp[i][j-1] + matrix[i][j]
• 이어서 i를 1부터 n-1까지 반복하며 세로 방향 누적합을 더합니다.
  • dp[i][j] += dp[i-1][j]
• 쿼리 메서드 sumRegion(row1, col1, row2, col2)는 포함-배제 원리를 사용합니다.
  • ret = dp[row2][col2] : (0,0)부터 (row2,col2)까지의 전체 합
  • sub1 : row1 - 1 < 0이면 0, 아니면 dp[row1-1][col2] (위쪽 영역 제거)
  • sub2 : col1 - 1 < 0이면 0, 아니면 dp[row2][col1-1] (왼쪽 영역 제거)
  • row1 - 1 < 0 또는 col1 - 1 < 0이면 add = 0, 아니면 add = dp[row1-1][col1-1] (두 번 빠진 중첩 영역 복원)
  • ret - sub1 - sub2 + add를 반환합니다.

이 방식은 전처리에 O(n×m) 시간이 걸리지만, 이후 모든 범위 합 쿼리를 상수 시간에 처리할 수 있다는 장점이 있습니다.

예제 코드 (C++)

아래 구현 예제를 통해 더 자세히 이해해 보겠습니다.

#include <bits/stdc++.h>
using namespace std;
class NumMatrix {
    public:
    vector < vector <int>> dp;
    NumMatrix(vector<vector<int>>& matrix) {
        int n = matrix.size();
        if(!n) return;
        int m = matrix[0].size();
        dp = vector < vector <int>>(n, vector <int> (m));
        for(int i = 0; i < n; i++){
            for(int j = 0 ;j < m; j++){
                dp[i][j] = j - 1 < 0 ? matrix[i][j] : dp[i][j - 1] + matrix[i][j];
            }
        }
        for(int i = 1; i < n; i++){
            for(int j = 0; j < m; j++){
                dp[i][j] += dp[i - 1][j];
            }
        }
    }
    int sumRegion(int row1, int col1, int row2, int col2) {
        int ret = dp[row2][col2];
        int sub1 = row1 - 1 < 0 ? 0 : dp[row1 - 1][col2];
        int sub2 = col1 - 1 < 0 ? 0 : dp[row2][col1 - 1];
        int add = row1 - 1 < 0 || col1 - 1 < 0 ? 0 : dp[row1 - 1][col1 - 1];
        return ret - sub1 - sub2 + add;
    }
};
main(){
    vector<vector<int>> mat = {{3,0,1,4,2},{5,6,3,2,1},{1,2,0,1,5},{4,1,0,1,7},{1,0,3,0,5}};
    NumMatrix ob(mat);
    cout << ob.sumRegion(2,1,4,3) << endl;
    cout << ob.sumRegion(1,1,2,2) << endl;
    cout << ob.sumRegion(1,2,2,4) << endl;
}

입력

[[3,0,1,4,2],
[5,6,3,2,1],
[1,2,0,1,5],
[4,1,0,1,7],
[1,0,3,0,5]]
sumRegion(2,1,4,3)
sumRegion(1,1,2,2)
sumRegion(1,2,2,4)

출력

8
11
12