二进制字典树(01-Trie)

二进制字典树，也称为01-Trie，是一种专门用于存储数字二进制表示的字典树数据结构。它在解决异或相关问题、寻找最大/最小异或值以及位操作挑战方面表现出色，具有最优时间复杂度。

基本二进制字典树实现

二进制字典树从最高有效位开始逐位存储数字，实现高效的异或操作。

带异或操作的二进制字典树

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

class BinaryTrie {
private:
    struct TrieNode {
        TrieNode* children[2];
        int count;
        
        TrieNode() : count(0) {
            children[0] = children[1] = nullptr;
        }
    };
    
    TrieNode* root;
    static const int MAXBITS = 30; // 对于32位整数
    
public:
    BinaryTrie() {
        root = new TrieNode();
    }
    
    void insert(int num) {
        TrieNode* curr = root;
        for (int i = MAXBITS; i >= 0; i--) {
            int bit = (num >> i) & 1;
            if (!curr->children[bit]) {
                curr->children[bit] = new TrieNode();
            }
            curr = curr->children[bit];
            curr->count++;
        }
    }
    
    void remove(int num) {
        TrieNode* curr = root;
        for (int i = MAXBITS; i >= 0; i--) {
            int bit = (num >> i) & 1;
            if (curr->children[bit]) {
                curr = curr->children[bit];
                curr->count--;
            }
        }
    }
    
    int findMaxXor(int num) {
        TrieNode* curr = root;
        int maxXor = 0;
        
        for (int i = MAXBITS; i >= 0; i--) {
            int bit = (num >> i) & 1;
            int oppositeBit = 1 - bit;
            
            // 尝试走相反位以获得最大异或
            if (curr->children[oppositeBit] && curr->children[oppositeBit]->count > 0) {
                maxXor |= (1 << i);
                curr = curr->children[oppositeBit];
            } else if (curr->children[bit] && curr->children[bit]->count > 0) {
                curr = curr->children[bit];
            } else {
                return -1; // 字典树为空
            }
        }
        
        return maxXor;
    }
    
    int findMinXor(int num) {
        TrieNode* curr = root;
        int minXor = 0;
        
        for (int i = MAXBITS; i >= 0; i--) {
            int bit = (num >> i) & 1;
            
            // 尝试走相同位以获得最小异或
            if (curr->children[bit] && curr->children[bit]->count > 0) {
                curr = curr->children[bit];
            } else if (curr->children[1-bit] && curr->children[1-bit]->count > 0) {
                minXor |= (1 << i);
                curr = curr->children[1-bit];
            } else {
                return -1; // 字典树为空
            }
        }
        
        return minXor;
    }
    
    bool search(int num) {
        TrieNode* curr = root;
        for (int i = MAXBITS; i >= 0; i--) {
            int bit = (num >> i) & 1;
            if (!curr->children[bit] || curr->children[bit]->count == 0) {
                return false;
            }
            curr = curr->children[bit];
        }
        return true;
    }
};

int main() {
    BinaryTrie trie;
    vector<int> nums = {3, 10, 5, 25, 2, 8};
    
    cout << "插入数字：";
    for (int num : nums) {
        cout << num << " ";
        trie.insert(num);
    }
    cout << endl;
    
    cout << "\n异或操作：" << endl;
    for (int num : {4, 6, 15}) {
        cout << "与 " << num << "的最大异或：" << trie.findMaxXor(num) << endl;
        cout << "与 " << num << "的最小异或：" << trie.findMinXor(num) << endl;
        cout << "搜索 " << num << ": " << (trie.search(num) ? "找到" : "未找到") << endl;
        cout << endl;
    }
    
    return 0;
}

二进制字典树从MSB到LSB逐位存储数字。对于最大异或，我们尽可能选择相反的位。对于最小异或，我们尽可能选择相同的位。

最大异或子数组问题

使用二进制字典树和前缀异或技术找到任意子数组的最大异或值。

最大异或子数组

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

class XORSubarray {
public:
    // 简化版本，不跟踪范围
    int maxXorSubarraySimple(vector<int>& arr) {
        int n = arr.size();
        int maxXor = 0;
        int prefixXor = 0;
        
        BinaryTrie trie;
        trie.insert(0); // 插入0作为空前缀
        
        for (int i = 0; i < n; i++) {
            prefixXor ^= arr[i];
            maxXor = max(maxXor, trie.findMaxXor(prefixXor));
            trie.insert(prefixXor);
        }
        
        return maxXor;
    }
};

// 解决：给定数组，找到任意子集的最大异或
int maxSubsetXor(vector<int>& arr) {
    XORBasis basis;
    for (int num : arr) {
        basis.insert(num);
    }
    return basis.getMaxXor();
}

// 解决：检查目标是否可以通过异或某个子集形成
bool canFormTarget(vector<int>& arr, int target) {
    XORBasis basis;
    for (int num : arr) {
        basis.insert(num);
    }
    return basis.canForm(target);
}

int main() {
    vector<int> arr = {1, 2, 3, 4};
    XORSubarray solver;
    
    cout << "数组：";
    for (int x : arr) cout << x << " ";
    cout << endl;
    
    int simpleResult = solver.maxXorSubarraySimple(arr);
    cout << "简单方法结果：" << simpleResult << endl;
    
    // 用另一个数组测试
    vector<int> arr2 = {8, 1, 2, 12, 7, 6};
    cout << "\n数组2：";
    for (int x : arr2) cout << x << " ";
    cout << endl;
    
    int result2 = solver.maxXorSubarraySimple(arr2);
    cout << "最大异或子数组值：" << result2 << endl;
    
    return 0;
}

我们使用前缀异或性质：子数组[i,j]的异或 = prefixXor[j+1] ^ prefixXor[i]。对于每个位置，我们使用二进制字典树找到能给出最大异或的前缀。