<Trie> BOJ 13504 XOR 합

문제

주어진 수열의 연속된 부분 수열 중에서 XOR 합이 가장 큰 부분 수열의 XOR합을 구하는 문제

• 테스트 케이스 t < = 10
• 배열의 크기 N <= 100000

접근

• 1. 모든 부분수열의 XOR합을 구해보는 $O(tN^2)$는 문제에 적합하지 않다.
• 2. 0부터 배열의 마지막 인덱스 까지의 i에 대해 0부터 i까지의 수에 대한 XOR합을 안다고 할때 임의의 범위에 대한 XOR값을 어떻게 계산할까?
     
• 3. 2의 특징과 Trie를 이용하면 $O(tN)$에 문제 해결이 가능하다.
  • 3-1. 0부터 i번째까지의 부분수열의 XOR합을 누적하며 Trie에 저장한다.
  • 3-2. 현재까지의 XOR합과 XOR하여 가장 큰 결과를 낼 값을 Trie에서 찾는다.최대값 찾는 방법
  • 3-3. 찾은 최대값을 전역변수와 비교해 더 크다면 저장 그렇지 않다면 넘어간다.

  코드

• 주의 사항
  trie에 0을 꼭 먼저 넣어주어야하는데 0부터 i번째까지의 XOR합이 구할 수 있는 최대값이 될 수 있기 때문이다.

import java.io.*;
import java.util.*;

class Node {
    int[] children;
    boolean valid;

    Node() {
        children = new int[2];
        Arrays.fill(children, -1);
        valid = false;
    }
}

class Trie {
    ArrayList<Node> trie = new ArrayList<>();
    int root;

    int init() {
        Node x = new Node();
        trie.add(x);
        return trie.size() - 1;
    }

    Trie() {
        trie = new ArrayList<>();
        root = init();
    }

    void add(int n, int idx, int cur) {
        if (idx == -1) {
            trie.get(cur).valid = true;
            return;
        }

        int c = (n & (1 << idx)) > 0 ? 1 : 0;
        if (trie.get(cur).children[c] == -1) {
            int nex = init();
            trie.get(cur).children[c] = nex;
        }

        int nex = trie.get(cur).children[c];
        add(n, idx - 1, nex);
    }

    void add(int n) {
        add(n, 30, root);
    }

    int search(int n, int idx, int cur, int val) {
        if (idx == -1) {
            return val;
        }

        int c = (n & (1 << idx)) > 0 ? 1 : 0;
        c = 1 - c;
        if (trie.get(cur).children[c] == -1) {
            c = 1 - c;
        }
        val += (c << idx);

        int nex = trie.get(cur).children[c];
        return search(n, idx - 1, nex, val);
    }

    int search(int n) {
        return search(n, 30, root, 0);
    }

}

class baek__13504 {

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        int tc = Integer.parseInt(br.readLine());

        StringBuilder sb = new StringBuilder();
        while (tc-- > 0) {
            int n = Integer.parseInt(br.readLine());
            String[] temp = br.readLine().split(" ");
            Trie trie = new Trie();
            int ans = 0;
            //XOR값을 누적할 변수 입니다.
            int now = 0;
            trie.add(0);
            for (int i = 0; i < n; i++) {
                int num = Integer.parseInt(temp[i]);
                now ^= num;
                //XOR 누적 합을 trie에 추가
                trie.add(now);
                ans = Math.max(ans, trie.search(now) ^ now);
            }
            sb.append(ans + "\n");
        }

        System.out.print(sb);

    }
}