XOR ของ Submatrix Queries ใน C++

โจทย์

ได้รับเมทริกซ์ N×N และ queries แต่ละ query กำหนดมุมซ้ายบน (r1,c1) และมุมขวาล่าง (r2,c2) ของ submatrix ต้องการหา XOR ขององค์ประกอบทั้งหมดใน submatrix นั้น

ตัวอย่าง

Matrix:

1 2 3
4 5 6
7 8 9

Queries: (0,0,1,2) และ (1,2,2,2)
Output: 1, 15

คำอธิบาย

Query 1 (0,0 to 1,2): 1^2^3^4^5^6 = 1
Query 2 (1,2 to 2,2): 6^9 = 15

วิธีแก้ปัญหา: 2D Prefix XOR

สร้าง 2D Prefix XOR matrix โดยที่ pref[r][c] = XOR ของ submatrix จาก (0,0) ถึง (r,c)

สูตรคำนวณ prefix XOR:

// แถวแรก
pref[0][c] = pref[0][c-1] ^ mat[0][c]

// คอลัมน์แรก
pref[r][0] = pref[r-1][0] ^ mat[r][0]

// อื่นๆ
pref[r][c] = pref[r-1][c] ^ pref[r][c-1] ^ pref[r-1][c-1] ^ mat[r][c]

สูตร query submatrix (r1,c1) ถึง (r2,c2):

result = pref[r2][c2] 
       ^ (r1>0 ? pref[r1-1][c2] : 0)
       ^ (c1>0 ? pref[r2][c1-1] : 0)
       ^ (r1>0 && c1>0 ? pref[r1-1][c1-1] : 0)

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

#include <iostream>
#include <vector>
using namespace std;

class SubmatrixXOR {
    vector<vector<int>> pref;
    int n;
    
public:
    SubmatrixXOR(const vector<vector<int>>& mat) {
        n = mat.size();
        pref.assign(n, vector<int>(n, 0));
        
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                int val = mat[i][j];
                if (i > 0) val ^= pref[i-1][j];
                if (j > 0) val ^= pref[i][j-1];
                if (i > 0 && j > 0) val ^= pref[i-1][j-1];
                pref[i][j] = val;
            }
        }
    }
    
    int query(int r1, int c1, int r2, int c2) {
        int res = pref[r2][c2];
        if (r1 > 0) res ^= pref[r1-1][c2];
        if (c1 > 0) res ^= pref[r2][c1-1];
        if (r1 > 0 && c1 > 0) res ^= pref[r1-1][c1-1];
        return res;
    }
};

int main() {
    vector<vector<int>> mat = {
        {1, 2, 3},
        {4, 5, 6},
        {7, 8, 9}
    };
    
    SubmatrixXOR smx(mat);
    
    cout << "Query 1 (0,0,1,2): " << smx.query(0, 0, 1, 2) << endl;
    cout << "Query 2 (1,2,2,2): " << smx.query(1, 2, 2, 2) << endl;
    
    return 0;
}

ผลลัพธ์

Query 1 (0,0,1,2): 1
Query 2 (1,2,2,2): 15

Complexity

• Preprocess: O(N²)
• Query: O(1)
• Space: O(N²)

การขยาย: รองรับ Update (Dynamic)

หากต้องการ update ค่าในเมทริกซ์ ใช้ 2D Fenwick Tree (BIT) หรือ 2D Segment Tree ที่รองรับ XOR operation

สรุป

2D Prefix XOR เป็นเทคนิคมาตรฐานสำหรับ static submatrix XOR queries ใช้หลักการ inclusion-exclusion principle เหมือน 2D Prefix Sum แต่เปลี่ยน + เป็น ^ ใช้ได้กับ operation ใดๆ ที่เป็น Abelian group (associative, commutative, มี identity และ inverse)