Nie patrzyłem na inne rozwiązania, więc moje:
TL;DR:
- A^A = 0, więc można redukować czynniki występujące parzystą ilośc razy
- istnieje prosty wzór na xor liczb 0..n
Tablica A wygląda tak:
0
0^1
0^1^2
0^1^2^3
0^1^2^3^4
0^1^2^3^4^5
...
Teraz jeśli pytamy o wynik xora wszystkich elementów od A[X] do [Y], to wyjdzie coś takiego:
xor all:
5^6^7^8^9^10^11^12^13
5^6^7^8^9^10^11^12^13^14
5^6^7^8^9^10^11^12^13^14^15
5^6^7^8^9^10^11^12^13^14^15^16
5^6^7^8^9^10^11^12^13^14^15^16^17
5^6^7^8^9^10^11^12^13^14^15^16^17^18
5^6^7^8^9^10^11^12^13^14^15^16^17^18^19
5^6^7^8^9^10^11^12^13^14^15^16^17^18^19^20
Najpierw sprawdzamy czy Y-X jest parzyste - w tym przypadku jest, więc redukuje się cały czynnik A[X]:
xor all:
14
14^15
14^15^16
14^15^16^17
14^15^16^17^18
14^15^16^17^18^19
14^15^16^17^18^19^20
(gdyby było nieparzyste to różniłoby się tylko zxorowaniem z tym fragmentem).
Co dalej? Teraz co drugi czynnik występuje parzystą ilość razy. Więc skracamy sobie je wszystkie:
xor all
14
14
14^16
14^16
14^16^18
14^16^18
14^16^18^20
Teraz nie trzeba mieć mensy żeby zauważyć że to sie dalej skraca:
14^16^18^20
Xorujemy teraz kilka liczb parzystych. Jako że wszystkie są parzyste, możemy sobie podzielić je przez dwa, zxorować i pomnożyć przez dwa (bo wiemy że ostatni bit to zawsze zero) (dla nieparzystych algorytm taki sam, z poprawką na to że wiemy że ostatni bit to zawsze 1)
2*(7^8^9^10)
Już wygląda całkiem nieźle. Jedyne co zostało to policzenie xorów 7^8^9^10 (tzn. xorów N konsekturywnych liczb naturalnych). Xor liczb 0..n można policzyć w czasie O(1) np. tak:
if n % 2 == 1 {
result = (n % 4 == 1) ? 1 : 0;
} else {
result = (n % 4 == 0) ? n : n + 1;
}
A xor(A..B)
to ofc xor(0..A) ^ xor(0..B)
.
No i to rozwiązanie generalnie wygląda na wzorcówkę którą wkleiłeś (tylko kody które dałeś są bardziej "clever" zapisane, bo algorytmicy lubią takie sztuczki).