C++で整数ストリームから指定した整数との最大XORを求める方法

この問題では、以下のいずれかのタイプに該当するQ個のクエリが与えられます。

タイプ1 − 挿入 (1, i)：値iを持つ要素をデータ構造に追加します。

タイプ2 − findXOR (2, i)：データ構造内のすべての要素と要素iとのXORの最大値を求めます。

データ構造には、初期状態として要素0のみが含まれているものとします。

問題を理解するための例を見てみましょう。

入力

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

出力

15 15

説明

各クエリを順に処理すると、
(1, 9) => データ構造 => {9}
(1, 3) => データ構造 => {9, 3}
(1, 7) => データ構造 => {9, 3, 7}
(2, 8) => 最大XOR(_, 8) = 15（XOR(7, 8)）
(1, 5) => データ構造 => {9, 3, 7, 5}
(2, 12) => 最大XOR(_, 12) = 15（XOR(3, 12)）

解法アプローチ

この問題は、トライ（trie）と呼ばれる特殊な探索木データ構造を使うことで効率的に解くことができます。ここで使うトライは、各ノードが2つの子ノードを持ち、数値を2進数のビット列として格納するものです。

具体的な手順は次のとおりです。

• タイプ1のクエリが来た場合は、その数値の2進表現（32ビット分）を上位ビットから順にトライへ挿入します。
• タイプ2のクエリが来た場合は、与えられた値の各ビットに対応するパスをトライ上で探索します。このとき、可能な限り「反対のビット」の子ノードを選ぶことで、その桁のXORを1にでき、結果として最大XORが得られます。

この手法により、挿入も検索も1クエリあたりO(32)、すなわちビット長に比例した時間で処理できます。

トライについてさらに詳しく知りたい方は、「トライデータ構造」の解説記事をご参照ください。

ソリューションの動作を示すプログラム：

例

#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] = NULL;
    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 = 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 to the data Structure. value = "<<query[i][1]<<endl;
        }
        if(query[i][0] == 2){
            cout<<"The maximum XOR with "<<query[i][1]<<" is "<<solveQueryType2(root, query[i][1])<<endl;
        }
    }
    return 0;
}

出力

Value inserted to the data Structure. value = 9
Value inserted to the data Structure. value = 3
Value inserted to the data Structure. value = 7
The maximum XOR with 8 is 15
Value inserted to the data Structure. value = 5
The maximum XOR with 12 is 15