Contest Duration: - (local time) (100 minutes) Back to Home

## F - Range Xor Query Editorial by en_translator

$$a \oplus b$$ has $$0$$ as an identity and is associative, so it can be processed fast with a segment tree. The time complexity is $$O((N + Q) \log (N))$$. Also, if we can calculate $$f(i) = A_1 \oplus A_2 \oplus A_3 \oplus \dots \oplus A_i(f(0) = 0$$ fast enough, then the answer will be $$f(Y_i) \oplus f(X_i - 1)$$ by the property of xor (where $$f(0) = 0$$), so we can also use Fenwick tree (Binary indexed tree).

Fenwick tree and Segment tree are implemented in AtCoder Library (ACL), which will help you to skip some implementations.

posted:
last update: