Range Sum Query 2D Immutable ใน C++: หาผลรวมในสี่เหลี่ยม 2D

โจทย์

กำหนดเมทริกซ์ 2D ตอบคำถาม: หาผลรวมในสี่เหลี่ยมที่กำหนดโดยมุมซ้ายบน (row1, col1) และมุมขวาล่าง (row2, col2) เมทริกซ์ไม่เปลี่ยนแปลง (Immutable)

แนวคิด: 2D Prefix Sum (Integral Image)

สร้างเมทริกซ์ dp ขนาดเท่าเดิม โดย dp[i][j] = ผลรวมจาก (0,0) ถึง (i,j)
แล้วคำตอบ = dp[row2][col2] - dp[row1-1][col2] - dp[row2][col1-1] + dp[row1-1][col1-1]

ขั้นตอนสร้าง dp

1. n = rows, m = cols
2. คำนวณ prefix sum แนวนอน: dp[i][j] = (j>0 ? dp[i][j-1] : 0) + matrix[i][j]
3. คำนวณ prefix sum แนวตั้ง: dp[i][j] += (i>0 ? dp[i-1][j] : 0)

ตอบคำถาม sumRegion

ret = dp[row2][col2];
sub1 = (row1 > 0) ? dp[row1-1][col2] : 0;
sub2 = (col1 > 0) ? dp[row2][col1-1] : 0;
add  = (row1 > 0 && col1 > 0) ? dp[row1-1][col1-1] : 0;
return ret - sub1 - sub2 + add;

ตัวอย่างโค้ด C++

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

class NumMatrix {
    vector<vector<int>> dp;
public:
    NumMatrix(vector<vector<int>>& matrix) {
        int n = matrix.size();
        if (!n) return;
        int m = matrix[0].size();
        dp.assign(n, vector<int>(m, 0));
        
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                dp[i][j] = (j > 0 ? dp[i][j-1] : 0) + 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 > 0 ? dp[row1-1][col2] : 0;
        int sub2 = col1 > 0 ? dp[row2][col1-1] : 0;
        int add = (row1 > 0 && col1 > 0) ? dp[row1-1][col1-1] : 0;
        return ret - sub1 - sub2 + add;
    }
};

int 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; // 8
    cout << ob.sumRegion(1,1,2,2) << endl; // 11
    cout << ob.sumRegion(1,2,2,4) << endl; // 12
    return 0;
}

อินพุต / เอาต์พุต

Input: เมทริกซ์ 5x5 + 3 คำถาม

Output: 8 11 12

ความซับซ้อน

• Preprocess: O(n×m)
• Query: O(1)
• Space: O(n×m)