トライ木の基本構造と実装

トライ木（Trie）は、文字列や数値の検索・格納に特化した木構造データ構造です。各ノードが複数の子ノードを持ち、文字やビットによってパスを分岐させることで効率的な検索を実現します。

まずは、英文字からなる文字列を扱う基本的なトライ木の実装を見てみましょう。

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

const int MAX_NODE = 100010;
int nextNode[MAX_NODE][26];
int wordCount[MAX_NODE];
int nodeId = 0;

void addWord(char *str) {
    int current = 0;
    for (int i = 0; str[i]; i++) {
        int charIdx = str[i] - 'a';
        if (!nextNode[current][charIdx]) {
            nextNode[current][charIdx] = ++nodeId;
        }
        current = nextNode[current][charIdx];
    }
    wordCount[current]++;
}

int findWord(char *str) {
    int current = 0;
    for (int i = 0; str[i]; i++) {
        int charIdx = str[i] - 'a';
        if (!nextNode[current][charIdx]) {
            return 0;
        }
        current = nextNode[current][charIdx];
    }
    return wordCount[current];
}

int main() {
    int queryNum;
    scanf("%d", &queryNum);
    while (queryNum--) {
        char operation;
        char inputStr[MAX_NODE];
        scanf("%s %s", &operation, inputStr);
        if (operation == 'I') {
            addWord(inputStr);
        } else {
            printf("%d\n", findWord(inputStr));
        }
    }
    return 0;
}

この実装では、nextNode配列が各ノードの遷移先を管理し、wordCountが単語の終端ノードでの出現回数を記録します。根ノードは0番目として初期化され、新しいノードが必要な場合はnodeIdをインクリメントして割り当てます。

最大 XOR ペア問題への応用

トライ木の概念を拡張して、整数のビット表現を扱うことで、最大 XOR ペア問題を効率的に解くことができます。この問題では、与えられた数値の集合から二つの要素を選び、その排他的論理和（XOR）が最大になる値を求めます。

各整数を31ビットの二進数表現と見なし、ビットごとに0または1の分岐を持つトライ木を構築します。検索時には、各ビットで可能な限り反対のビットを持つ子ノードを選択することで、XOR値を最大化します。

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

const int MAX_NODES = 100010 * 31;
int children[MAX_NODES][2];
int nodeIndex = 0;

void addNumber(int value) {
    int pos = 0;
    for (int bitPos = 30; bitPos >= 0; bitPos--) {
        int bit = (value >> bitPos) & 1;
        if (!children[pos][bit]) {
            children[pos][bit] = ++nodeIndex;
        }
        pos = children[pos][bit];
    }
}

int findMaxXor(int value) {
    int pos = 0;
    int maxXor = 0;
    for (int bitPos = 30; bitPos >= 0; bitPos--) {
        int bit = (value >> bitPos) & 1;
        if (children[pos][1 - bit]) {
            maxXor |= (1 << bitPos);
            pos = children[pos][1 - bit];
        } else {
            pos = children[pos][bit];
        }
    }
    return maxXor;
}

int main() {
    int elementCount;
    cin >> elementCount;
    int numbers[elementCount + 1];
    for (int i = 1; i <= elementCount; i++) {
        cin >> numbers[i];
        addNumber(numbers[i]);
    }
    
    int answer = 0;
    for (int i = 1; i <= elementCount; i++) {
        answer = max(answer, findMaxXor(numbers[i]));
    }
    cout << answer << endl;
    return 0;
}

このアルゴリズムの鍵は、各数値をビット単位で処理し、可能な限り反対のビットを辿ることでXOR値をビルドアップしていく点です。children配列は各ノードの0と1への遷移を管理し、findMaxXor関数が最大XOR値を計算します。