Binary Trie (01-Trie)

Binary Trie, also known as 01-Trie, is a specialized trie data structure for storing binary representations of numbers. It excels at solving XOR-related problems, finding maximum/minimum XOR values, and bit manipulation challenges with optimal time complexity.

Basic Binary Trie Implementation

A Binary Trie stores numbers bit by bit, starting from the most significant bit, enabling efficient XOR operations.

Binary Trie with XOR Operations

#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; // For 32-bit integers
    
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;
            
            // Try to go to opposite bit for maximum XOR
            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; // Trie is empty
            }
        }
        
        return maxXor;
    }
    
    int findMinXor(int num) {
        TrieNode* curr = root;
        int minXor = 0;
        
        for (int i = MAXBITS; i >= 0; i--) {
            int bit = (num >> i) & 1;
            
            // Try to go to same bit for minimum XOR
            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; // Trie is empty
            }
        }
        
        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 << "Inserting numbers: ";
    for (int num : nums) {
        cout << num << " ";
        trie.insert(num);
    }
    cout << endl;
    
    cout << "\nXOR Operations:" << endl;
    for (int num : {4, 6, 15}) {
        cout << "Max XOR with " << num << ": " << trie.findMaxXor(num) << endl;
        cout << "Min XOR with " << num << ": " << trie.findMinXor(num) << endl;
        cout << "Search " << num << ": " << (trie.search(num) ? "Found" : "Not found") << endl;
        cout << endl;
    }
    
    return 0;
}

Binary Trie stores numbers bit by bit from MSB to LSB. For max XOR, we choose opposite bits when possible. For min XOR, we choose same bits when possible.

Maximum XOR Subarray Problem

Find the maximum XOR value of any subarray using Binary Trie with prefix XOR technique.

Maximum XOR Subarray

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

class XORSubarray {
public:
    // Simpler version without range tracking
    int maxXorSubarraySimple(vector<int>& arr) {
        int n = arr.size();
        int maxXor = 0;
        int prefixXor = 0;
        
        BinaryTrie trie;
        trie.insert(0); // Insert 0 for empty prefix
        
        for (int i = 0; i < n; i++) {
            prefixXor ^= arr[i];
            maxXor = max(maxXor, trie.findMaxXor(prefixXor));
            trie.insert(prefixXor);
        }
        
        return maxXor;
    }
};

// Solve: Given array, find maximum XOR of any subset
int maxSubsetXor(vector<int>& arr) {
    XORBasis basis;
    for (int num : arr) {
        basis.insert(num);
    }
    return basis.getMaxXor();
}

// Solve: Check if target can be formed by XORing some subset
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 << "Array: ";
    for (int x : arr) cout << x << " ";
    cout << endl;
    
    int simpleResult = solver.maxXorSubarraySimple(arr);
    cout << "Simple method result: " << simpleResult << endl;
    
    // Test with another array
    vector<int> arr2 = {8, 1, 2, 12, 7, 6};
    cout << "\nArray 2: ";
    for (int x : arr2) cout << x << " ";
    cout << endl;
    
    int result2 = solver.maxXorSubarraySimple(arr2);
    cout << "Maximum XOR subarray value: " << result2 << endl;
    
    return 0;
}

We use prefix XOR property: XOR of subarray [i,j] = prefixXor[j+1] ^ prefixXor[i]. For each position, we find the prefix that gives maximum XOR using Binary Trie.