01 사전 트 리 요약

예전 에는 사전 나무 가 별로 쓸모 가 없다 고 생각 했 지만 최근 에 관련 된 문 제 를 만 나 정리 하려 고 합 니 다.그 중 하 나 는 01 사전 트 리 문제 라 고 하 는데 xor (비트 연산) 를 해결 하 는 유력 한 무기 입 니 다. 보통 배열 을 주 고 연속 적 인 차이 점 이나 최대 가 얼마 인지 물 어보 면 01 사전 트 리 로 빨리 해결 할 수 있 고 실현 하기에 도 편리 합 니 다.
다른 성질:  1. 교환 율  2. 결합 율, 즉 (a ^ b) ^ c = a ^ (b ^ c))  3. 자 반성, 즉 x ^ x = 0  4. x^0=x 
그 중에서 가장 많이 활용 되 는 것 은 자 반성 이다.
다음 템 플 릿 문제 드 리 겠 습 니 다.
전송 문: 클릭 하여 링크 열기
제목: 몇 개의 수 를 정 하고 이 수의 차이 나 값 이 가장 큰 값 을 구하 세 요.
분석: 각 수 를 매 거 하여 X 로 한 다음 에 trie 에서 가능 한 한 X 의 바 이 너 리 와 반대 되 는 수 를 찾 아 답 을 계속 업데이트 합 니 다.
코드:

#include
#include
#include
using namespace std;
const int N = 1e5+5;
int n,cnt,a[N];

struct trie{
    int nt[2];
    int val;
}tr[32*N];

void build(int x) {
    int rt=0;
    for(int i=31;i>=0;i--) {
        int c=(x>>i)&1;
        if(!tr[rt].nt[c]) tr[rt].nt[c]=++cnt;
        rt=tr[rt].nt[c];
    }
    tr[rt].val=x;
}

int query(int x) {
    int rt=0;
    for(int i=31;i>=0;i--) {
        int c=(x>>i)&1;
        if(tr[rt].nt[c^1]) rt=tr[rt].nt[c^1];
        else rt=tr[rt].nt[c];
    }
    return tr[rt].val^x;
}

int main(){
    ios::sync_with_stdio(0);
    while(cin>>n) {
        cnt=0;
        memset(tr,0,sizeof(tr));
        for(int i=0;i>a[i];
            build(a[i]);
        }
        int mx=-1;
        for(int i=0;i