h3. **Xor Max**

Fie {$X{~i~} = A{~1~} xor A{~2~} xor ... xor A{~i~}$}. Pentru fiecare $X{~i~}$ vom incearca sa gasim un $X{~j~}$ ({$j < i$}) astfel incat $X{~i~} xor X{~j~}$ sa fie maxim. Pentru a realiza aceasta operatie eficient vom mentine un *trie* (vezi in CLR varianta in romana la pagina 223 - capitolul "Arbori binari de cautare" problema 13-2 - se asemana cu "suffix trees/tries" doar ca vom lucra cu siruri binare). Fie $b$ numarul maxim de biti pe care ii are un element din vector. Vom realiza operatia de gasire a lui $X{~j~}$ in {$O(b)$}. Structura de date mentionata mai sus va memora sirurile de biti formate de vectorul {$X$}. Vom parcurge bitii lui $X{~i~}$ de la cel mai semnificativ la cel mai nesemnificativ. Astfel daca bitul curent este {$1$}, vom incerca sa gasim un sir de biti care are acest bit $0$ (pentru a maxima xor-ul), iar daca bitul curent este $0$ vom proceda invers. Complexitatea finala a algoritmului este {$O(N*b)$}.

Fie {$X{~i~} = A{~1~} xor A{~2~} xor ... xor A{~i~}$}. Pentru fiecare $X{~i~}$ vom incearca sa gasim un $X{~j~}$ ({$j < i$}) astfel incat $X{~i~} xor X{~j~}$ sa fie maxim. Pentru a realiza aceasta operatie eficient vom mentine un *trie* (vezi in CLR varianta in romana la pagina 223 - capitolul "Arbori binari de cautare" problema 13-2 - se asemana cu "suffix trees/tries" doar ca vom lucra cu siruri binare, nu cu litere). Fie $b$ numarul maxim de biti pe care ii are un element din vector. Vom realiza operatia de gasire a lui $X{~j~}$ in {$O(b)$}. Structura de date mentionata mai sus va memora sirurile de biti formate de vectorul {$X$}. Vom parcurge bitii lui $X{~i~}$ de la cel mai semnificativ la cel mai nesemnificativ. Astfel daca bitul curent este {$1$}, vom incerca sa gasim un sir de biti care are acest bit $0$ (pentru a maxima xor-ul), iar daca bitul curent este $0$ vom proceda invers. Complexitatea finala a algoritmului este {$O(N*b)$}.

h3. **Boom**