Tìm XOR lớn nhất của số nguyên cho trước trong luồng số nguyên bằng Trie trong C++

Cấu trúc dữ liệu ban đầu chỉ chứa số 0.

Ví dụ minh họa

Đầu vào:

Truy vấn: (1, 9), (1, 3), (1, 7), (2, 8), (1, 5), (2, 12)

Đầu ra:

15 15

Giải thích:

(1,9) → DS = {9}
(1,3) → DS = {9,3}
(1,7) → DS = {9,3,7}
(2,8) → max XOR(_,8) = 15 (từ 7^8)
(1,5) → DS = {9,3,7,5}
(2,12) → max XOR(_,12) = 15 (từ 3^12)

Phương pháp giải quyết

Sử dụng Trie nhị phân (Binary Trie) - cây tìm kiếm đặc biệt nơi mỗi nút có 2 con (bit 0 và bit 1).

• Chèn (Type 1): Thêm biểu diễn nhị phân 32-bit của số vào Trie.
• Truy vấn (Type 2): Để tối đa XOR, ta cố gắng đi ngược bit của số truy vấn tại mỗi cấp độ (nếu bit truy vấn là 0 thì ưu tiên đi nhánh 1, và ngược lại). Kết quả xây dựng được là giá trị XOR lớn nhất.

Chương trình minh họa

#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 << "Đã chèn giá trị: " << query[i][1] << endl;
        }
        if (query[i][0] == 2) {
            cout << "Max XOR với " << query[i][1] << " là " << solveQueryType2(root, query[i][1]) << endl;
        }
    }
    return 0;
}

Kết quả đầu ra

Đã chèn giá trị: 9
Đã chèn giá trị: 3
Đã chèn giá trị: 7
Max XOR với 8 là 15
Đã chèn giá trị: 5
Max XOR với 12 là 15