Range XOR Queries with Updates
An integer array receives a stream of two kinds of queries: set position i to value v, or report the bitwise XOR of all elements from l to r inclusive. Answer every query efficiently.
- 1 ≤ n, q ≤ 2 · 10^5
- 0 ≤ a[i], v < 2^30
- 0 ≤ l ≤ r < n
- XOR is associative and invertible — a range can be combined from pieces
- Updates interleaved with range queries
- Same shape as range sum with a different combine operator
Prefix sums break the moment the array changes, since every prefix after the update shifts. A Fenwick or segment tree stores partial aggregates over power-of-two ranges so both a point update and a range query touch only O(log n) nodes. Use a sparse table instead when the array is static and the operation is idempotent (min, max, gcd).
Use a segment tree whose nodes store the XOR of their range; XOR is associative, so any node value is the XOR of its two children. Updates rewrite a leaf and recompute ancestors; queries combine O(log n) disjoint nodes covering [l, r]. Because XOR is its own inverse, a Fenwick tree over prefix XORs also works: answer [l, r] as prefix(r) ⊕ prefix(l - 1).
- Without updates, a prefix-XOR array answers queries in O(1). Sqrt decomposition trades to O(√n) per operation with trivial code.