หาค่า XOR สูงสุดกับจำนวนเต็มที่กำหนดในสตรีมข้อมูลด้วย Trie ใน C++

คำอธิบายปัญหา

ได้รับคิวรี (Queries) จำนวน Q คิวรี แต่ละคิวรีเป็นหนึ่งในสองประเภท:

• Type 1 (Insertion): (1, i) → เพิ่มค่า i เข้าไปในโครงสร้างข้อมูล
• Type 2 (Query): (2, i) → หา ค่า XOR สูงสุด ระหว่าง i กับสมาชิกทุกตัวในโครงสร้างข้อมูลปัจจุบัน

โครงสร้างข้อมูลมีค่าเริ่มต้นเพียงค่าเดียวคือ 0

ตัวอย่าง

Queries: (1, 9), (1, 3), (1, 7), (2, 8), (1, 5), (2, 12)

Output: 15 15

คำอธิบาย:

• Insert 9, 3, 7 → Set = {9, 3, 7}
• Query 8: Max XOR กับ 8 คือ 15 (จาก 7^8 = 15)
• Insert 5 → Set = {9, 3, 7, 5}
• Query 12: Max XOR กับ 12 คือ 15 (จาก 3^12 = 15)

แนวทางแก้ปัญหา: Trie (Prefix Tree)

ใช้ Binary Trie ที่แต่ละโหนดมีลูก 2 ตัว (Bit 0 และ Bit 1) เพื่อเก็บการแทนค่าบाइनารีของตัวเลข (32-bit)

การทำงาน:

1. Insert (Type 1): แปลงตัวเลขเป็น 32-bit แล้วเพิ่มเข้า Trie ตาม Bit แต่ละตำแหน่ง (จาก MSB ไป LSB)
2. Query (Type 2): เพื่อหา Max XOR ให้พยายามเดินทางใน Trie ไปทางตรงข้ามกับ Bit ของค่าที่ Query (ถ้า Bit เป็น 0 ให้เดินทางไป 1, ถ้า 1 ให้เดินทางไป 0) เพื่อให้ได้ Bit ผลลัพธ์เป็น 1 มากที่สุด

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

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

struct Trie {
    Trie* children[2];
    bool isLeaf;
};

bool check(int N, int i) {
    return (bool)(N & (1 << i));
}

Trie* newNode() {
    Trie* temp = new Trie;
    temp->isLeaf = false;
    temp->children[0] = temp->children[1] = NULL;
    return temp;
}

void insertVal(Trie* root, int x) {
    Trie* val = root;
    for (int i = 31; i >= 0; i--) {
        int f = check(x, i);
        if (!val->children[f])
            val->children[f] = newNode();
        val = val->children[f];
    }
    val->isLeaf = true;
}

int solveQueryType2(Trie *root, int x) {
    Trie* val = root;
    int ans = 0;
    for (int i = 31; i >= 0; i--) {
        int f = check(x, i);
        if (val->children[f ^ 1]) {  // พยายามเดินทางตรงข้าม
            ans += (1 << i);
            val = val->children[f ^ 1];
        } else {
            val = val->children[f];
        }
    }
    return ans;
}

void solveQueryType1(Trie *root, int x) {
    insertVal(root, x);
}

int main() {
    int Q = 6;
    int query[Q][2] = {{1, 9}, {1, 3}, {1, 7}, {2, 8}, {1, 5}, {2, 12}};
    Trie* root = newNode();
    
    for (int i = 0; i < Q; i++) {
        if (query[i][0] == 1) {
            solveQueryType1(root, query[i][1]);
            cout << "Value inserted: " << query[i][1] << endl;
        }
        if (query[i][0] == 2) {
            cout << "Max XOR with " << query[i][1] << " is " << solveQueryType2(root, query[i][1]) << endl;
        }
    }
    return 0;
}

ผลลัพธ์

Value inserted: 9
Value inserted: 3
Value inserted: 7
Max XOR with 8 is 15
Value inserted: 5
Max XOR with 12 is 15