h3. Xor Max

Fie X[i] = A[1] xor A[2] 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). 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